2

I have fairly large dictionary (200K words, 2-16 chars length) and various input strings (5-200 words separated by spaces, 2-20 chars length). Using PHP in cli mode I need to compare each input word to words in dictionary and calculate minimum levenshtein distance with almost maximum efficiency - how can I do it?

What I have already tried:

  1. Implemented my own basic comparison algorithm (with exponential complexity) - very slow.
  2. Implemented my own advanced comparison algorithm (based on words length) - faster, but still very slow.
  3. Converted dictionary into Trie data structure and implemented search in a Trie - faster than p.2, but still not enough.
  4. Added extra hashtable for cases when input word match dict word (zero distance). Also input words with calculated distance are put into hashtable so they are not calulated twice when repeated in input string. STILL NOT FAST ENOUGH.

What I'm thinking of:

  1. Precalulating Trie nodes for dictionary as the latter never changes.
  2. Using arrays instead of objects for Trie nodes.
  3. Implementing another algorithm? Like n-grams or levenshtein automata? Not sure whether it is worth it.
Alexander Dyachkov
  • 328
  • 1
  • 9
  • I've read that one. Not much comparison of trie nodes, n-grams and levenshtein automata methods. Or arrays vs objects as tries. For example I've read that levenshtein automata is probably the best option, but don't have enough proofs from practical point of view. – Alexander Dyachkov Feb 27 '17 at 10:54

0 Answers0