Вычисление коэффициента совпадения строк

[grumblerbear]

Здравствуйте, уважаемые математики и не совсем математики!

Так как сам я в этой теме не силен, то прошу прощения, если создал тему не в той ветке — думаю, администратор сможет перенести ее, если что-то не так.

Задача оказалась не совсем тривиальной (по крайней мере для меня).
Приступлю к описанию:
Существует алгоритм, который нормализует строки (так скажем, минимизирует возможные опечатки в них) (алгоритм MetaPhone, адаптированный под русский язык [http://web.archive.org/web/20071107145942/http://kankowski.narod.ru/dev/metaphoneru.htm] и адаптированный мной под нужды задачи).
И существует другой алгоритм, в котором эти нормализированные строки перемалываются и вычисляются определенные переменные. На основе этих переменных нужно составить формулу, результат которой будет соответствовать идентичности строк (от 0 до 100 или от 0 до 1).

Приведу пример:

Сравниваемая строка: «ПУШКИН»
Эталонная строка «АЛИКСАНДРСИРГИИВИЧПУШКИН»

$A$: количество похожих чанков: 5
$B$: количество идущих подряд похожих чанков: 5
$N$: количество несовпадающих чанков: 0
$D$: разница в количестве чанков: 18
$E$: количество чанков в эталонной строке: 23
$C$: количество чанков в сравниваемой строке: 5

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

В случае строки «ПУШКИН», чанки получаются такими: ПУ, УШ, ШК, КИ, ИН

Мной использовались варианты:
$A \cdot 2 / (E + C)$ - плохие результаты
$A / E$ - плохие результаты
$(A + B) / (E + C)$ - средние результаты
Ну и + с различными вариациями $D$ и $N$ в формуле. Либо было неуниверсально, либо слишком далеко от реальности

Буду рад дискуссии и помощи

Deggial: формулы поправил, формулы оформляйте $\TeX$ом. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).

[provincialka]

А в чем все-же задача? Найти подстроку? Или еще что? Возьмите чанк длиной 6 - вот и все

[grumblerbear]

Не найти. А узнать коэффициенты схожести строк и выбрать несколько самых похожих.
Например при запросе ПУШКИН у строки АЛИКСАНДРСИРГИИВИЧПУШКИН процент похожести будет в районе процентов 60. А у ДАНТЕС — 0.
Это нужно для того, чтобы я мог понять, что хочет пользователь, даже если он запросит что-то с опечатками или не полностью введет запрос.
Понимаете соль?

Кстати за правку формул спасибо тому, кто это сделал. Не думал что у вас тут все так серьезно организовано :) Но это к лучшему

[arseniiv]

grumblerbear в сообщении #729455 писал(а):

$A \cdot 2 / (E + C)$ - плохие результаты
$A / E$ - плохие результаты
$(A + B) / (E + C)$ - средние результаты

Что означают «плохие» и «средние»? Это ведь как раз соль — какие результаты должны быть. Тогда будет ясно (или так и не ясно), что делать.

[grumblerbear]

Выше я привел пример «предполагаемых значений».
Из всех точно известных данных: при отсутствии совпадений процент идентичности равен 0, при абсолютном совпадении строк - 100%. При этом возрастание коэффициента не должно быть линейным. Совпадающие подряд чанки должны повышать его сильнее чем просто совпадающие.

[url]http://lacony.ru/facts/metaphone/?test=ЛЮБОЙВАШТЕКСТ[/url]
Вот ссылка для примера, по которой к строкам вычисляются переменные для формулы.

[provincialka]

Ваше затруднение не в формуле, а в идеологии. Вы хотите вычислить числовой коэффициент неизвестно для чего. В таких задачах надо сначала построить модель, хоть как-то формализовать желаемое, прежде, чем искать формулу. И вот этого мы за вас сделать не сможем.

[arseniiv]

grumblerbear в сообщении #729787 писал(а):

Совпадающие подряд чанки должны повышать его сильнее чем просто совпадающие.

Агааа! Ну вот, значит, натяните на независимые компоненты $(A,B,N,D,E,C)$ пространство и нарисуйте там желаемую поверхность. А уже потом попробуйте её как-то формулой описать. Такое пространство, конечно, не очень наглядно, так что придётся выделить меньшее количество факторов. Например, убрать двоих из $(D,E,C)$ (один из них явно избыточен), зато поделив на них (например, на среднее их арифметическое или что-то такое) остальные.

[grumblerbear]

Числовой коэффициент количества совпадений в строках.
Привожу примеры:
Две строки.

Запрошенная - 10 чанков, сравниваемая с ней (эталонная) 20 чанков.
Абсолютная идентичность - 100%
10 совпадений, 10 подряд приблизительно 65-75%
10 совпадений, 5 подряд приблизительно 45-55%
10 совпадений, из них ни одного подряд приблизительно 25-35%
Ни одного совпадения - 0%

Запрошенная - 20 чанков, сравниваемая с ней (эталонная) 20 чанков.
Абсолютная идентичность - 100%
19 совпадений, 19 подряд приблизительно 85-100%
15 совпадений, 10 подряд приблизительно 65-85%
10 совпадений, из них ни одного подряд приблизительно 15-25%
Ни одного совпадения - 0%

Примерное представляете? Примеры с Пушкиным здесь просто так. Пользователи будут искать холодильники, котят и сиськи, или что там обычно в наших интернетах ищут. Неважно.

-- 28.05.2013, 23:22 --

arseniiv в сообщении #729792 писал(а):

grumblerbear в сообщении #729787 писал(а):

Совпадающие подряд чанки должны повышать его сильнее чем просто совпадающие.

Агааа! Ну вот, значит, натяните на независимые компоненты $(A,B,N,D,E,C)$ пространство и нарисуйте там желаемую поверхность. А уже потом попробуйте её как-то формулой описать. Такое пространство, конечно, не очень наглядно, так что придётся выделить меньшее количество факторов. Например, убрать двоих из $(D,E,C)$ (один из них явно избыточен), зато поделив на них (например, на среднее их арифметическое или что-то такое) остальные.

Можете подсказать какую область теории изучать? А то я как-то с натягиванием пространства не знаком...

[arseniiv]

Даже не знаю какую. Тут, вроде, никакой и нет. Один здравый смысл — может быть, тут мы в границах его применимости.

Ага, вот вы привели некоторые значения функции от $(E,C,A,B)$. Попробуйте теперь избавиться от раздельной её зависимости от $E$ и $C$, а так же от $A$ и $B$ — может, это осмысленно. Попробуйте, например, сделать функцию от $C/E$ и $B/A$, каждый параметр лежит в $[0; 1]$, как и результат. И рисовать линии уровня на квадрате $[0; 1]\times [0; 1]$ несложно.

Если такая модель никак не позволяет добиться желаемого, пошевелите её немного. Добавьте нелинейности.

[grumblerbear]

Спасибо огромное. Попытаюсь.

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

[grumblerbear]

Пока остановился на формуле $((A / C \cdot (1/3)) + (B / C \cdot (2/3)) - (N / C \cdot (1/10)) - (D / E \cdot (1/10))) \cdot 100$