[squeak-dev] [ANN] [Cuis] Cuis 2.1 is available. Lots of cool stuff inside!

Leandro caniglia at dm.uba.ar
Sat Feb 13 15:43:30 UTC 2010


Thank you for remarking this. Could you please suggest a reference where 
I can learn more about the O(n+m) algorithm? (Note however that our 
"trick" could also be useful with the fast algorithm because it avoids 
comparing individual words of lines that are common).


Levente Uzonyi wrote:
> On Fri, 12 Feb 2010, Leandro wrote:
>> Levente Uzonyi wrote:
>>       You can also get the word based diff using TextDiffBuilder by 
>> subclassing it and overriding #split:. Actually ClassDiffBuilder does 
>> exactly
>>       this, so using ClassDiffBuilder instead of TextDiffBuilder will 
>> give you the expected result.
>> I think that the difference with the implementation Valeria and I did 
>> is that ours switches from lines to words automatically. It also 
>> defines "words"
>> as Smalltalk words, meaning that it understands keyword limits, which 
>> gives better results. The differentiator starts comparing lines, and 
>> if the
>> proportion of line differences isn't too high, then it reutilizes the 
>> work already done (with lines) and refines it to get differences in 
>> between
>> keywords. The refining strategy was crucial for achieving good 
>> performance.
> If you subclass ClassDiffBuilder (let's call the subclass 
> KeywordDiffBuilder)
> and implement KeywordDiffBuilder >> #split: just like DifferenceFinder 
> >> #keywordsAndBlanksFrom: you get even better results.
> DifferenceFinder has to use such tricks/hacks to have good 
> performance, because it uses the simplest lcs algorithm which requires 
> n*m time and space in all cases, while for practical cases 
> TextDiffBuilder requires O(n+m) time and space.
> Levente
>> Not sure if the full functionality I'm describing here is in the last 
>> Cuis version though.
>> /Leandro

More information about the Squeak-dev mailing list