On Monday, February 5, 2018 at 1:53:06 PM UTC+1, Borneq wrote:
> W dniu 05.02.2018 o 10:31, M.M. pisze:
> > Dziedzina wiedzy dziedziną wiedzy, ale porównania się robi i używa się
> > do tego analogicznych algorytmów jak do porównywania ciągów znaków.
>
> Czytałem o algorytmie Myersa wspaniale wytłumaczonym na blogu jcoglan.
> Znajduje maksymalny wspólny podciąg, ale rozwiązań może być wiele. W
> podstawowej wersji ma tę miłą właściwość że gromadzi inserty i delety
> razem. Jednak wersja profesjonalna, używająca liniowego a nie
> kwadratowego miejsca pamięci, nie ma tej właściwości.
> Przykład:
> https://blog.jcoglan.com/2017/03/22/myers-diff-in-li
near-space-theory/
>
> Jak można by to poprawić? Może najpierw rekurencyjnie dzielić na bloki,
> ale gdy blok nie przekracza 50 wierszy, robić wersję standardową?
> Poza tym, implementacja Butlera z CodeProject dla liniowego:
> 782104906830590
> 683059078210490
> daje lepsze rezultaty niż można by się spodziewać.
>
> Git ma jeszcze możliwość opcji --patience, która poprawia, jednak
> wyszukując unikalne wiersze - nie nadaje się np. do genomu.

Z tego co pobieżnie kiedyś dawno temu przeglądałem, to temat jest
niebagatelny, ponieważ istnieje wiele heurystyk. Poszczególne
heurystyki różnie podnoszą skuteczność pamięciową i/albo obliczeniową
w zależności od danych; głównie chodzi o to, na ile porównywane
podciągi są podobne. Przy złożoności obliczeniowej M*N
ciężko policzyć dla choćby miliona genów, nie wspominając o
pamięciowej.

Pozdrawiam