2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Вычисление коэффициента совпадения строк
Сообщение28.05.2013, 13:18 
Здравствуйте, уважаемые математики и не совсем математики!

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

Задача оказалась не совсем тривиальной (по крайней мере для меня).
Приступлю к описанию:
Существует алгоритм, который нормализует строки (так скажем, минимизирует возможные опечатки в них) (алгоритм 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$ в формуле. Либо было неуниверсально, либо слишком далеко от реальности

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

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

 
 
 
 Re: Вычисление коэффициента совпадения строк
Сообщение28.05.2013, 22:30 
Аватара пользователя
А в чем все-же задача? Найти подстроку? Или еще что? Возьмите чанк длиной 6 - вот и все :D

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

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

 
 
 
 Re: Вычисление коэффициента совпадения строк
Сообщение28.05.2013, 22:42 
grumblerbear в сообщении #729455 писал(а):
$A \cdot 2 / (E + C)$ - плохие результаты
$A / E$ - плохие результаты
$(A + B) / (E + C)$ - средние результаты
Что означают «плохие» и «средние»? Это ведь как раз соль — какие результаты должны быть. Тогда будет ясно (или так и не ясно), что делать.

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

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

 
 
 
 Re: Вычисление коэффициента совпадения строк
Сообщение28.05.2013, 23:03 
Аватара пользователя
Ваше затруднение не в формуле, а в идеологии. Вы хотите вычислить числовой коэффициент неизвестно для чего. В таких задачах надо сначала построить модель, хоть как-то формализовать желаемое, прежде, чем искать формулу. И вот этого мы за вас сделать не сможем.

 
 
 
 Re: Вычисление коэффициента совпадения строк
Сообщение28.05.2013, 23:12 
grumblerbear в сообщении #729787 писал(а):
Совпадающие подряд чанки должны повышать его сильнее чем просто совпадающие.
Агааа! Ну вот, значит, натяните на независимые компоненты $(A,B,N,D,E,C)$ пространство и нарисуйте там желаемую поверхность. А уже потом попробуйте её как-то формулой описать. Такое пространство, конечно, не очень наглядно, так что придётся выделить меньшее количество факторов. Например, убрать двоих из $(D,E,C)$ (один из них явно избыточен), зато поделив на них (например, на среднее их арифметическое или что-то такое) остальные.

 
 
 
 Re: Вычисление коэффициента совпадения строк
Сообщение28.05.2013, 23:21 
Числовой коэффициент количества совпадений в строках.
Привожу примеры:
Две строки.

Запрошенная - 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)$ (один из них явно избыточен), зато поделив на них (например, на среднее их арифметическое или что-то такое) остальные.

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

 
 
 
 Re: Вычисление коэффициента совпадения строк
Сообщение29.05.2013, 00:52 
Даже не знаю какую. Тут, вроде, никакой и нет. :roll: Один здравый смысл — может быть, тут мы в границах его применимости.

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

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

 
 
 
 Re: Вычисление коэффициента совпадения строк
Сообщение29.05.2013, 01:18 
Спасибо огромное. Попытаюсь.

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

 
 
 
 Re: Вычисление коэффициента совпадения строк
Сообщение29.05.2013, 13:29 
Пока остановился на формуле $((A / C \cdot (1/3)) + (B / C \cdot (2/3)) - (N / C \cdot (1/10)) - (D / E \cdot (1/10))) \cdot 100$

 
 
 [ Сообщений: 11 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group