nltk/nltk — Issue #117: nltk.containers.Trie.find_prefix returns None on matches that are substrings of another match
Author: alexrudnick
Created: 2012-01-17 06:26:28+00:00
State: open

This minimal test case shows the behaviour:

from nltk.containers import Trie
t = Trie()
t["A"] = "a"
t["B"] = "abc"
assert t.find_prefix("abd") == ("A", "bd")

Here is a modified implementation that matches the documentation better:

def find_prefix(self, key):
"""
Find as much of the key as one can, by using the longest
prefix that has a value. Return (value, remainder) where
remainder is the rest of the given string.
"""
curr_node = self.root
remainder = key
longest = None
for ch in key:
if curr_node[0]:
longest = (curr_node[0], remainder)
try:
curr_node = curr_node[1][ch]
except KeyError:
break
remainder = remainder[1:]
if not curr_node[0] and longest:
return longest
return (curr_node[0], remainder)

If the current behaviour is desired, the documentation should be updated to
mention that you will get this behaviour on keys which are substrings of
other keys.

Migrated from http://code.google.com/p/nltk/issues/detail?id=557

earlier comments

xim@8d.no said, at 2011-05-30T23:53:27.000Z:

I agree that the curent implementation of find_prefix isn't the most useful. Some comments:

* Your test case doesn't make sense. «t.find_prefix("abd")» is (None, 'abd') and that is always correct.
* In your implementation, you use «if curr_node[0]:» where you should test with «is None».
* I'm using this code, and what i actually want is the current behaviour. I don't want the values, though - I want the subtrie starting at that level.

Current behaviour:

>>> t = nltk.containers.Trie()
>>> t['OneTwo'] = 'foo'
>>> t.find_prefix('OneSeven')
(None, 'Seven')

What I think the reporter wants (intuitive because there is no data stored on any prefix of 'OneSeven'):

>>> t.find_prefix('OneSeven')
(None, 'OneSeven')

What I want:

>>> t.find_prefix('OneSeven')
(, 'Seven')

The best may be to keep the current default behaviour, and add and option for only returning prefixes that has a value assigned (if one exists). For the behaviour I want, it might be more appropriate to add a find_prefix_subtrie()?

If anyone concurs, I'll hack it together =)