search

AleksandrHovhannisyan / Python-Trie-Implementation

Python trie implementation, for educational purposes
5 stars 4 forks source link

Partial-Match Searching #1

Open joe63 opened 2 years ago

joe63 commented 2 years ago

Would it be possible to extend your implementation with a function : Partial-Match Searching F.i. pmsearch(root, 'a.a.a.' ) like in the DrDobbs Article from 1998? Thanks in advise.

AleksandrHovhannisyan commented 2 years ago

Hi! I'm not familiar with that article so I'm not sure, but the main use case for prefix trees is partial-match searching. Could you clarify what you mean in that example you shared? What words are in the dictionary and what are you searching for?

joe63 commented 2 years ago

Hi , thank you for yor fast response!

====> if name == 'main': trie = PrefixTree() trie.insert('apple') trie.insert('app') trie.insert('aposematic') trie.insert('appreciate') trie.insert('book') trie.insert('bad') trie.insert('bear') trie.insert('bat')

for example 👍 trie.pmsearch('ba.') should deliver: bad and bat the dot is a Wildcard.

BR Johann

AleksandrHovhannisyan commented 2 years ago

Oh, gotcha. The approach covered in this article should support that since it's just a prefix tree, so the prefix you're searching for in that example case is 'ba' (no need to specify a wildcard selector). See this section for reference: https://www.aleksandrhovhannisyan.com/blog/trie-data-structure-implementation-in-python/#3-return-a-list-of-all-nodes-starting-with-a-given-prefix.

joe63 commented 2 years ago

HI, I see, my example(did not descibe my really need) could be solved with the starts_with-function.

I need a function which allows wildcard within the string: if name == 'main': trie = PrefixTree() trie.insert('apple') trie.insert('app') trie.insert('aposematic') trie.insert('appreciate') trie.insert('book') trie.insert('bad') trie.insert('bear') trie.insert('bat') trie.insert('care') trie.insert('core')

trie.pmsearch('c.re') or also trie.pmsearch('c.r.') should deliver: care and core

BR Johann

AleksandrHovhannisyan commented 2 years ago

Oh, I see. I'm not sure how I'd approach that. Sounds like you'd need to consider multiple tree paths when encountering a wildcard character and then aggregate all the matching paths into one final list.