Re: [boost] [gsoc 2013] Approximate string matching

Subject: Re: [boost] [gsoc 2013] Approximate string matching
From: Bjorn Reese (breese_at_[hidden])
Date: 2013-04-13 08:30:11

On 04/13/2013 01:45 PM, Jan Strnad wrote:
> Dne 13.4.2013 10:41, Bjorn Reese napsal(a):
>> On 04/12/2013 11:52 AM, Jan Strnad wrote:
>>
>>> In the matter of NFA implementation, I would probably choose dynamic
>>> programming approach, but I'm thinking of shift-or algorithm as well.
>>
>> You may also want to look into Thomson NFAs:
>>
>>     http://swtch.com/~rsc/regexp/regexp1.html
>>
>>
> When I was writing about NFA I actually meant Thomson like NFA -- no
> backtracking required.

Maybe I was a bit to brief in my previous reply. What I meant was that
you should consider, as an alternative to dynamic programming and
shift-or, to execute the NFA in a simulation as described in the above
link. This is just a suggestion though.