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

Subject: Re: [boost] [gsoc 2013] Approximate string matching
From: Jan Strnad (hanny.strnad_at_[hidden])
Date: 2013-04-13 08:39:41

Dne 13.4.2013 14:30, Bjorn Reese napsal(a):
> 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.
>
Sure, I understood you in the first place. I'm considering all 
possibilities including NFA simulation. All I meant is that at this 
moment dyn. prog. approach is suits the problem in my opinion the best. 
I can't think of any advantage of NFA simulation against dyn. prog., and 
I only see disadvantages (preprocessing required, higher memory 
requirements).