Задача сравнения похожих строк встречается на практике довольно часто: лично я недавно столкнулся с ней при попытке импорта почтовых адресов из одной программы в другую.
Например, один адрес может выглядеть как «Тверская обл., Кашин г, Советская ул, 1, 5», а другой – как «Тверская область; город Кашин; улица Советская; дом 1; квартира 5». Похожи ли эти строки и насколько? Несомненно, похожи. И «невооруженным глазом» видна их структура: область – населенный пункт – улица – дом – квартира. Логично, что для адресов важно такое разбиение строк на группы; то есть сравнивать мы должны не «две каши» из сходных слов (где одна «каша» состоит из слов первой строки, а вторая – из слов второй), а именно осуществлять «погруппное» сравнение слов из первой строки со словами из второй. Просматривается и критерий разбиения на группы: в первой строке разделителем групп является «, », а во второй – «; ».
Читать полностью »