Разрабатываю библиотечку для сравнения строк с образцами. Возник вопрос который больше идеологически, нежели технический. Упрощённо говоря суть в следующем.
Задан образец некой фразы, состоящей из нескольких слов
p1 p2 ... pN
С ним сравнивается фраза, из такого же количества слов
w1 w2 ... wN
Т.е. слова разделены пробелами или ещё чем нибудь, не важно - и мы просто сравниваем каждое слово w с соответствующим по порядку образцом p. Результатом такого сравнения является, какой-то критерий e, например, количество опечаток (от 0 до length(p)) - или в принципе какая-то "похожесть" в промежутке [0, 1]... или ошибочность (в том же промежутке... или от 1 до +inf... Критериев можно много придумать и их несложно друг из друга получить... В общем, будет у нас N оценок:
e1, e2, ... eN.
Так вот. Вопрос в том - как оценить "похожесть" (или "релевантность") полного образца (из N элементов) и целой фразы (из N элементов).
Например, сначала я использовал для соответсвия слова элементу образца критерий "ошибочность" (от 0.0 до 1.0) и для фразы в целом брал "ошибочность" как max{e}.
Однако, получалось что если скажем у меня четыре слова, и три из них без ошибок, а в одном ошибочность равна 0.5, то фраза целиком не проходила, если порог установлен например 0.3.
Тогда я стал считать их среднее геометрическое. Точнее среднее геометрическое величин, дополняющих "ошибочность" до 1 (назовём это "похожестями"):
etotal = 1 - (П(1-ei))1/N
С этой оценкой хорошо то, что если одна из "ошибочностей" равна 1.0, то и общая ошибочность тоже будет 1.0, а если все "ошибочности" равны, то общая "ошибочность" равна ошибочности каждого из элементов.
Теперь однако выходит что если, например, сравнивается фраза из 3 слов и из них два безошибочны, то третье может иметь ошибочность около 0.65... Т.е. в общем оно может оказаться почти непохожим на элемент образца.
Ну и хуже всего что мне не хватает знаний чтобы решить, разумен ли в общем случае какой-то из этих способов - или может лучше использовать какой-то другой, а также чтобы обдумать возможные сложности которых я пока не нашёл. Проблема в том что я потихоньку внедряю этот функционал в проект и полезно заранее продумать возможные косяки, т.к. когда он уже хорошо внедрится, переделывать будет гораздо сложнее.
Так что буду рад и благодарен любым подсказкам, советам, идеям и возражениям.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
30:21:31
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
30:21:31
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 11:13:30 (f1).
Десктопная версия, переключиться на мобильную.
При поддержке
Скажем "Барак Х Обама 2" - здесь два имени собственных, аббревиатура и числовое значение.
Т.е. я исхожу из пожелания, что механизм должен быть робастным - т.е. чтобы он был адекватен для возможно большего количества случаев, хотя может механизмы заточенные под специальные случаи вели бы себя лучше для этих специальных случаев и хуже для остальных.
Т.е. станции могут быть записаны сокращённо, с ошибками или вообще нестандартно. Кроме того есть станции с похожими названиями:
Московская - Маяковская
Московская - Московские ворота
Ленинский проспект - площадь Ленина (проспект и площадь могут сокращаться до пр. и пл. например, ну и "ленинский" может быть написан не полностью)
Невский проспект, он же Канал Грибоедова, он же Гостиный двор. К "каналу" может быть присобачена "наб."...
Площадь Александра Невского - может иметь довольно много вариантов сокращений
В общем получается есть одна строчка и полсотни образцов. Мне хотелось создать механизм который бы позволял удобно перечислить эти образцы, скажем, в массиве - а потом вызывать для каждой проверяемой строки единственную функцию для выбора лучшего совпадения... Я об этом в прошлом посте жаловался...
В общем, механизм-то я создал, но тут заметил что благодаря подстановкам, кроме метро им ещё много вещей можно обрабатывать в моём проекте, например запись размера может быть:
* просто числом "50"
* диапазоном "30-40"
* с присловьем "от 30", "меньше 40" или "от 30 до 40"
Или название предмета:
* стиральная машина (стир.маш. и т.п.);
* автомобиль (машина и т.п.)
* холодильник (2-дв х-к и т.п.)
Так что задачи стали довольно общими...
Конечно при задании мне приходится учитывать различные возможные варианты (этого за меня комп не осилит), но по крайней мере они сводятся в одну строку, например вышеупомянутый размер записывается через "ИЛИ" из следующих альтернатив:
* ЧИСЛО заменяется на "ЧИСЛО ЧИСЛО"
* ("до" или "меньше") ЧИСЛО заменяется на "0 ЧИСЛО"
* ("от" или "больше") ЧИСЛО заменяется на "ЧИСЛО INF"
* ЧИСЛО1 ("-" ИЛИ ":" ИЛИ "/") ЧИСЛО2 заменяется на "ЧИСЛО1 ЧИСЛО2"
* "от" ЧИСЛО1 "до" ЧИСЛО2 заменяется на "ЧИСЛО1 ЧИСЛО2"
Получается что-то вроде... Хм... В общем я не нашёл как тут тег "pre" сделать, сорри... %)
Исправление опечаток обычно эквивалентно максимизации некоторой величины, и очень важно понимать её физический смысл. В Вашем случае это, скорее всего, условная вероятность того, что пользователь имел ввиду pi при условии, что он писал wi. Стоит заметить, в самой распространённой существующей модели ошибок (noisy channel) эта условная вероятность равна P(p)/P(w)*П(1-ei). (здесь P - частота конкретной фразы среди всех запросов). Чтобы сэкономить Вам время скажу по поводу модели "noisy channel", что если 1-ei = exp(-dist(pi, wi)), где dist - почти симметричная относительно свапа p и w функция, то Вы скорее всего довольно близки к этой модели. Если считать P(w) фиксированным, то задача состоит в максимизации произведения P(p)*П(1-ei). Обычно имеет смысл делать замену если P(p)/P(w)*П(1-ei) - величина порядка единицы. При этом для вычисления P разумно пользоваться чем-нибудь типа статистического словаря и считать все слова независимыми. Тогда общая формула превратится в П(P(pi)/P(wi)*(1-ei)). И именно эту величину разумно сравнивать с каким-нибудь 0.7.