REKLAMA

Algorytm porównania plików tekstowych

Podróż po algorytmach tekstowych, którą odbyliśmy w poprzedniej części serii, była dla mnie naprawdę fascynująca. Kto by pomyślał, że takie proste – wydawałoby się – zagadnienie, jakim jest przetwarzanie tekstu, może być takie ciekawe? Ostatnio zainteresowałem się więc kolejnym algorytmem, który dziś weźmiemy na warsztat, a jest nim  poszukiwanie najdłuższego wspólnego podciągu albo, mówiąc prościej, wyznaczaniem różnic edycyjnych pomiędzy dwoma ciągami.

Zagadnienia poruszane w tym artykule:

  • Magia;
  • Odległość;
  • Diagram edycj;
  • Algorytm prosty;
  • Przenieśmy się więc do Arizony;
  • Algorytm zachłanny;
  • Optymalizacja pamięciowa;
  • Docelowy algorytm;
  • Implementacja;
  • Porównywanie tekstów;

Artukuł pochodzi z magazynu Programista nr 91 (4/2020). Jest to wydanie z przełomu czerwca i lipca 2020 r. Szczegółowy spis treści wydania nr 91: https://programistamag.pl/programista-4-2020-91/

Autorem artykułu jest Wojciech Sura. Programuje od 25 lat, z czego 10 komercyjnie; ma na koncie aplikacje desktopowe, webowe, mobilne i wbudowane - pisane w C#, C++, Javie, Delphi, PHP, Javascript i w jeszcze kilku innych językach. Obecnie pracuje w firmie WSCAD, rozwijającej oprogramowanie nowej generacji CAD dla elektrotechników.