4 ms·

The basic trie only matches exact consecutive characters. Does anyone know the data structure/trie variant for matching partial sequential characters? e.g.

The basic trie only matches exact consecutive characters. Does anyone know the data structure/trie variant for matching partial sequential characters? e.g. ABD matches A Brown Dog ^ ^ ^

js_chap 5y ago
You probably want fuzzy search: https://en.m.wikipedia.org/wiki/Approximate_string_matching https://en.m.wikipedia.org/wiki/Approximate_string_matching
Rd6n6 5y ago
Or for common misspellings on mobile?
aelzeiny 5y ago
There's a searching concept known as edit (levenshtein) distance that is close but not exactly what you're talking about. To rephrase your question: is there a datastructure that can pre-compute the levenshtein distance for a set or results? Yes, and it's crazy complicated. See Levenshtein Automata[1]. In reality, I would let the professionals handle this by either using Open/ElasticSearch or Apache Lucene. [1]http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levensht...
- harry8 5y ago
  >I would let the professionals handle this... If this site doesn't contain "the professionals" then the phrase has zero meaning.
  - aelzeiny 5y ago
    Fair enough. "Crazy complicated" and "the professionals" are both intended as subjective terms. To ME this stuff might as well be magic.
    - harry8 5y ago
      I'd flip that and decide that there is no algorithm that exists and is documented that you can't implement yourself, for amusement and educational value or, given time and the will, more than that. Just making that decision has value for you even if you don't actually do it terribly often. Same as you can design a cpu in HDL and flash it to an FPGA. (The "Nand to Tetris" course seems popular) Same as you can write an OS. Same as you can write a compiler and/or interpreter. Believing these things (and they're actually true!) gets us all away from learned helplessness. There's enough of that when it comes to actual silicone... Nobody understands it all. _You_ understand as much of it as you choose, in the direction that takes you, as deep as you want to go. It's just work, a lot of it, but no more than that.
- Cybiote 5y ago
  An in-between option that is relatively simple and a rather fast (though not as fast as the automata) optimization to levenstein distance and based on Tries is: http://stevehanov.ca/blog/?id=114 http://stevehanov.ca/blog/?id=114.
TYMorningCoffee 5y ago
Not exactly what you want but a second trie with the key on the starting letters and the value the complete word might work for you. Your ABD example would work but something like ABrD would not.
deckard1 5y ago
If I understand correct, you're wondering how you might match "a bro do" with "a brown dog" or "a brown door", etc. Similar to what Google does. I've done this before. It's not a single data structure, but a process. First, you normalize your strings to index (convert to lower case, throw out stop words such as "a", "the", "is", etc.) then you generate prefixes (or n-grams, I suppose). Say you want to do musicians and you have "Bob Dylan" as an entry. That would become "bob dylan" which would generate the prefixes "bo", "bob", "bob d", etc. You include spaces but once you hit a space, you start generating new prefixes. So you would also start doing "dy", "dyl", "dyla", and "dylan". The max length of the prefixes depends on how much memory you're willing to use. Lets say Bob Dylan is mapped to some musician table in your DB and he has id 1000. I've done this with Redis, but you can use a trie as well. You'd store every prefix in the trie and the data on the node would be an array of musician ids. Now the magic: if you search "bo dyl" you would look up the prefix "bo", grab all the ids and then look up the prefix "dyl" and grab the ids (you would also try the full "bo dyl" first, but let's just assume nothing is there). Once you have those two arrays, you would take the intersection of them. Which, in our case, would leave an array containing id = 1000 along with any others that matched both. That's, in general, how a simple autocomplete works. But you're better off using Redis or Elasticsearch if your data set is large. And if it's not, well... a simple hashmap is probably competitive and easier than tries.
padolsey 5y ago
A quick hack for this is to create variations and include them in your main trie (with links to the canonical value/object/etc.). E.g. you might create a variation w/o vowels. There are heuristics you can apply here rather than implementing full fuzziness or levenshtein comparators etc. Ultimately it depends on your use-case and what common variations users might try to use.

The basic trie only matches exact consecutive characters. Does anyone know the data structure/trie variant for matching partial sequential characters? e.g. ABD matches A Brown Dog ^ ^ ^

js_chap 5y ago

You probably want fuzzy search: https://en.m.wikipedia.org/wiki/Approximate_string_matching https://en.m.wikipedia.org/wiki/Approximate_string_matching

Rd6n6 5y ago

Or for common misspellings on mobile?

aelzeiny 5y ago

There's a searching concept known as edit (levenshtein) distance that is close but not exactly what you're talking about. To rephrase your question: is there a datastructure that can pre-compute the levenshtein distance for a set or results? Yes, and it's crazy complicated. See Levenshtein Automata[1]. In reality, I would let the professionals handle this by either using Open/ElasticSearch or Apache Lucene. [1]http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levensht...

harry8 5y ago
>I would let the professionals handle this... If this site doesn't contain "the professionals" then the phrase has zero meaning.
- aelzeiny 5y ago
  Fair enough. "Crazy complicated" and "the professionals" are both intended as subjective terms. To ME this stuff might as well be magic.
  - harry8 5y ago
    I'd flip that and decide that there is no algorithm that exists and is documented that you can't implement yourself, for amusement and educational value or, given time and the will, more than that. Just making that decision has value for you even if you don't actually do it terribly often. Same as you can design a cpu in HDL and flash it to an FPGA. (The "Nand to Tetris" course seems popular) Same as you can write an OS. Same as you can write a compiler and/or interpreter. Believing these things (and they're actually true!) gets us all away from learned helplessness. There's enough of that when it comes to actual silicone... Nobody understands it all. _You_ understand as much of it as you choose, in the direction that takes you, as deep as you want to go. It's just work, a lot of it, but no more than that.
Cybiote 5y ago
An in-between option that is relatively simple and a rather fast (though not as fast as the automata) optimization to levenstein distance and based on Tries is: http://stevehanov.ca/blog/?id=114 http://stevehanov.ca/blog/?id=114.

TYMorningCoffee 5y ago

Not exactly what you want but a second trie with the key on the starting letters and the value the complete word might work for you. Your ABD example would work but something like ABrD would not.

deckard1 5y ago

If I understand correct, you're wondering how you might match "a bro do" with "a brown dog" or "a brown door", etc. Similar to what Google does. I've done this before. It's not a single data structure, but a process. First, you normalize your strings to index (convert to lower case, throw out stop words such as "a", "the", "is", etc.) then you generate prefixes (or n-grams, I suppose). Say you want to do musicians and you have "Bob Dylan" as an entry. That would become "bob dylan" which would generate the prefixes "bo", "bob", "bob d", etc. You include spaces but once you hit a space, you start generating new prefixes. So you would also start doing "dy", "dyl", "dyla", and "dylan". The max length of the prefixes depends on how much memory you're willing to use. Lets say Bob Dylan is mapped to some musician table in your DB and he has id 1000. I've done this with Redis, but you can use a trie as well. You'd store every prefix in the trie and the data on the node would be an array of musician ids. Now the magic: if you search "bo dyl" you would look up the prefix "bo", grab all the ids and then look up the prefix "dyl" and grab the ids (you would also try the full "bo dyl" first, but let's just assume nothing is there). Once you have those two arrays, you would take the intersection of them. Which, in our case, would leave an array containing id = 1000 along with any others that matched both. That's, in general, how a simple autocomplete works. But you're better off using Redis or Elasticsearch if your data set is large. And if it's not, well... a simple hashmap is probably competitive and easier than tries.

padolsey 5y ago

A quick hack for this is to create variations and include them in your main trie (with links to the canonical value/object/etc.). E.g. you might create a variation w/o vowels. There are heuristics you can apply here rather than implementing full fuzziness or levenshtein comparators etc. Ultimately it depends on your use-case and what common variations users might try to use.