3 ms·
How would you use this to find a small string (or string close to it) in a large fixed corpus? Usually you want to find many small strings in a large corpus.
by amelius 5y ago
How would you use this to find a small string (or string close to it) in a large fixed corpus?
Usually you want to find many small strings in a large corpus.
- kreeben 5y agoOne of the most efficient ways (that I know of) is to create a trie [0] from your corpus, then incorporate the levenshtein algo into the tree traversal algo to give you a levenshtein automata over a trie. Since a trie is a binary tree, if it's properly balanced, this timing of this operation is O(log(n)). A less efficient way is to traverse the trie and calculate the Levenshtein distance for each word you encounter. An even less efficient solution might be to sort all strings in your corpus by length and calculate distance for all of them. [0] https://en.wikipedia.org/wiki/Trie https://en.wikipedia.org/wiki/Trie