reduction

[Ben Bacarisse]

Ian Kelly <ian.g.kelly at gmail.com> writes:

> On Tue, May 31, 2016 at 8:22 AM, Fillmore <fillmore_remove at hotmail.com> wrote:
>>
>> My problem. I have lists of substrings associated to values:
>>
>> ['a','b','c','g'] => 1
>> ['a','b','c','h'] => 1
>> ['a','b','c','i'] => 1
>> ['a','b','c','j'] => 1
>> ['a','b','c','k'] => 1
>> ['a','b','c','l'] => 0  # <- Black sheep!!!
>> ['a','b','c','m'] => 1
>> ['a','b','c','n'] => 1
>> ['a','b','c','o'] => 1
>> ['a','b','c','p'] => 1
>>
>> I can check a bit of data against elements in this list
>> and determine whether the value to be associated to the data is 1 or 0.
>>
>> I would like to make my matching algorithm smarter so I can
>> reduce the total number of lists:
>>
>> ['a','b','c','l'] => 0  # If "l" is in my data I have a zero
>> ['a','b','c'] => 1      # or a more generic match will do the job
>>
>> I am trying to think of a way to perform this "reduction", but
>> I have a feeling I am reinventing the wheel.
>>
>> Is this a common problem that is already addressed by an existing module?
>
> Sounds like you probably want a trie data structure. You can google
> for Python implementations.

And, possibly, the related notion of a "suffix tree".

-- 
Ben.