Поиск похожих названий

    Как я уже написал в предисловии на странице Физики, данный пример явился результатом задания по сжатию базы данных, содержащей названия улиц. Маркетинговая компания использовала эти данные в своих исследованиях по опросам аудитории СМИ (средств массовой информации). Названия улиц фигурировали в адресах респондентов, участвующих в опросах. В такой сфере деятельности особое внимание уделяется достоверности данных, а система сбора данных о респондентах такова, что эти данные переводятся в электронный вид самыми разными способами, различными людьми в различных городах России. Поэтому проблема повторяемости и даже искажения данных стояла достаточно остро.

Вы можете сами пополнить предлагаемую базу данных по аналогии с уже имеющимися данными.
Программа предназначена для Visual Foxpro 5 и выше и очень наглядно демонстрирует свойства алгоритма. Несмотря на EXE-расширение, она запускается только из интегрированной среды Visual Foxpro. Обязательно прочитайте файл "Readme.txt" внутри архива.

Правило формирования коэффициента похожести.

Для тех, кто капельку знаком с теорией кодирования и передачи информации сразу скажу основную суть правила формирования ключа (т.е. коэффициента похожести, а скорее, наоборот, различия):

ключ формируется по правилу Хэмминга.

Как говорится, спасибо за вопрос.
Для  ответа на него следует обратиться к теории метрических пространств.
    Рассмотрим множество, состоящее из всевозможных текстовых строк ограниченной длины. Это можество будет у нас являться пространством, точками которого являются текстовые строки (т.е. одна строка - это одна точка, разные строки - разныые точки, одинаковые строки - одна и та же точка).
    Мы хотим научиться как-нибудь измерять расстояние между точками этого пространства. Тогда и можно будет говорить о "похожести": чем ближе точки, тем похожей соответствующие текстовые строки.

Определение. Метрическим пространством называется множество, для которого существует функция от двух переменных, заданная на парах точек этого множества, и обладающая свойствами расстояния.

В этом случае про значение функции на паре точек можно говорить, что оно является расстоянием между этими двумя точками множества. При этом можно рисовать точки на бумаге, например, и не задумываться о природе множества. А саму функцию можно называть расстоянием , или метрикой.
(Какими свойствами обладает расстояние, нас и вас учили еще в пятом классе: неравенство треугольника и т.д.)

Для рассматриваемого случая в качестве метрики была выбрана идея Хэмминговой метрики. Применяться она должна следующим образом:
Если текстовые строки имеют одинаковую длину, то расстояние между ними - это количество несовпадающих символов.
Если текстовые строки имеют разнуюую длину, то расстояние между ними - это чуть сложнее.
Для определенности в этом случае следует считать, что все строки имеют одинаковую длину (вспомним, ведь их длина ограничена каким-то числом, вот оно и будет длиной всех строк, а оставшуюся часть, где реальная строка кончается, можно заполнить например символом ACII=0). Тогда длина таких двух строк расчитывается как в первом случае.

На этом можно было бы поставить точку. Но...

Оказалось, что можно улучшить алгоритм, рассматривая несколько иное метрическое пространство, учитывающее особенности, оторые влияли на ошибки при вводе текстов. Например, при вводе соседние буквы иногда переставляются местами, или нажимается соседняя клавиша, или дважды одна и та же буква, или случайно прпускается какая-то буква и т.п. Я рассуждал так. Представьте, что слово один раз ввелось правильно, а во второй раз пропустили первую букву.  В результате вся строка сдвинулась влево по сравнению с первой. Если применять правило сравнения в лоб, то эти два слова будут несовпадать в кадой позиции, и значи очень сильно отличаться друг от друга. Хотя на самом деле расстояние между ними хотелось бы получить минимальным.
К тому же латинские буквы вообще можно   игнорировать, если их одна-две. Цифры и знаки пунктуации в названиях улиц также можно не рассматривать и т.п.  Тем самым размер текстоой строки уменьшается.

Исходя из этих соображений я реализовал следующий алгоритм:
Берем строки длиной в 256 символов. Они и будут у нас точками метрического постранства. Каждой позиции соответствует ASCII код с номером позиции. Отсчет позиций, поэтому ведем от 0 до 255.

При сравнении полученных строк игнорируем позиции, соответствующие в ASCII кодировке всей нижней половине таблицы. Т.о. остаются только верхние 128 символов. Среди них игнорируем символы псевдографики, нижний и верхний регистр будем считать совпадающими. Остаются только 32 буквы русского алфавита. Это и будет длина текстовой строки. Повторы букв в словах не учитываем. Легко видеть, как подобное построение можно распространить и на другие виды кодировок.

Расстояние между строками и этолоном рассчитывается так:
Берем эталон. Если в нем присутствует буква "А", заносим "1" в соответствующюю позицию. Если в нем присутствует буква "Б", заносим "1" в соответствующюю позицию. Если в нем присутствует буква "В", заносим "1" ... Понятно? Остальные позиции заполняются нулями.
В результате будет сформирована строка из "0" и "1".

Также поступаем со сравниваемой строкой.
В результате будет сформирована еще одно строка из "0" и "1".
Расстояние между ними - это количество отличающихся позиций.
Эта величина и отражена на рисунке в поле "Ключ" в нижнем списке.


Теперь должно быть понятным, что листать нижний список далеко вниз не имеет смысла. Если значение ключа больше, например, 10, то названия улиц скорее всего сильно не похожи друг на друга.

Потму, что несмотря на существование встроенной функции в языке программирования, а в данном случае это был Visual FoxPro v.5.0, и несмотря на то, что это была русская версия, функция эта никак не хотела работать с русским текстом. (Она и для английского-то текста выдает только четыре уровня отличий).