WordSyn: алгоритм работы с двухсловниками
Итак, пришло время доделать давно обещанную фичу: обработку текстов с использованием статистических данных по двухсловным комбинациям.
Перед тем, как приступать к разработке этого блока, я решил формализовать алгоритм его работы.
Исходные данные: есть база данных, содержащая несколько одинаковых таблиц, содержащих данные по статистике использования следующих комбинаций частей речи:
- существительное - существительное (кошкин дом)
- существительное - прилагательное (ясное солнце)
- существительное - глагол (муха летит)
- наречие - прилагательное (слегка пьяный)
- наречие - глагол (быстро идти)
Как вы понимаете, разбиение на пары по частям речи нужно для того, чтобы значительно уменьшить время поиска. И это, кстати, все равно стоит делать, так как моя программа “знает”, к каким частям речи относится каждое из обрабатываемых слов. При этом во время обработки будут проверяться как прямые пары, так и обратные. К примеру, словосочетания “быстрый конь” и “кот ученый” должны будут проверяться по одной и той же таблице “существительное-прилагательное”, но в разной последовательности.
База данных получена после обработки почти 76 тысяч произведений, в сумме занимающих 14 гигабайт.
Алгоритм работы модуля должен быть следующим:
- Разбиваем текст на слова
- Для всех слов находим все возможные синонимы
- Здесь у нас начало цикла попарной обработки исходных слов
- Если грамматические классы слов пары не принадлежат ни к одной из перечисленных выше комбинаций, то идем в начало цикла
- Составляем список со всеми возможными комбинациями пар синонимов к обрабатываемой паре. Допустим, у слова W1 есть два синонима W1S1 и W1S2, а у слова W2 есть аж три синонима W2S1, W2S2 и W2S3. Поэтому у нас в списке будет шесть пар, начинающихся с “W1S1-W2S1″ и заканчивающихся “W1S2-W2S3″.
- Проверяем наличие каждой из пар в нашем справочнике (согласно грамматическим классам) и отбрасываем те пары, которые в нем не встречаются ни разу. Таким образом мы избавимся от тех пар, которые ни разу не встречались в литературе. Допустим, три пары не были найдены и мы их отбросили. В результате мы получили следующий список (цифры обозначают количество раз, сколько данная пара встречалась в обработанных текстах):
W1S1 - W2S2 - 1002
W1S1 - W2S3 - 5034
W1S2 - W2S2 - 2048 - Теперь нам останется только выбрать ту пару, которая встречалась наибольшее количество раз, и задачу подбора наиболее оптимальных синонимов для данной пары слов можно считать выполненной.
- Переходим в начало цикла, если это была не последняя пара слов оригинального текста.
К сожалению, данный подход имеет несколько недостатков. Самый главный из них - отсутствие проверки контекста. К сожалению, постройка системы, которая будет понимать контекст, очень серьезная и сложная задача, и я уверен, что мне она не по плечу.
Но выход из положения все же есть. Для этого мы должны обрабатывать слова не парами, а тройками. При этом в пункте 5 мы будем должны найти синонимы для трех слов, а затем составить два списка, которые будут содержать пары синонимов для каждой из пар слов из оригинальной тройки. Таким образом второй список будет содержать пары начиная с “W2S1-W3S1″ и заканчивая “W2S3-W3Sx”, где W3Sx - последний синоним третьего слова. Затем (в пункте 6) мы очистим от неизвестных пар оба списка, и перейдем к пункту 7, в котором все, что нам будет нужно сделать, так это найти такие комбинации синонимов из первого и второго списка, чтобы значение “W1Sx-W2Sy” + “W2Sy-W3Sz” было как можно большим.
Естественно, что даже такой подход не даст нам максимальной уверенности в том, что результирующий текст будет приемлемым, хоть эта уверенность и будет выше, чем в случае использования отдельных пар.
Дальнейшие улучшения алгоритма могут быть следующими:
- используем пары, но при этом делаем два прохода. Второй проход должен начинаться со второго слова. Таким образом мы первый раз пройдемся по парам, начинающихся с нечетных слов, а второй раз - с четных. Минус такого подхода, что во втором проходе мы будем искать синонимы к синонимам, что может здорово исказить текст.
- Используем тройки, которые идут внахлест: W1-W2-W3, W3-W4-W5 и так далее. Минус этого подхода такой же, как и в первом случае - во второй итерации мы будем работать с синонимами синонимов слова W3.
- Используем тройки без нахлеста, а потом проверяем значения функций попарно, пытаясь найти максимальное значение. Минус этого подхода - большая трудо- и ресурсоемкость процесса.
Буду рад, если кто-то прочтет этот пост до конца и напишет в комментариях свое мнение по этому поводу. Думаю, скорое решение этого вопроса будет интересно каждому из владельцев моего синонимайзера. Разве что за исключением тех, кто им не пользуется.
Загрузка ...
05.02.2009 в 08:46
А как дела с тематичностью текстов в твоей базе ? Насколько считаешь её полной ? И как вообще считаешь правильным оценивать качество базы ?
05.02.2009 в 09:49
Как уже было сказано, в этой базе будут только слова, которые моя программа “знает”. Таким образом в словаре не будет слов “попса” или “ЖК”, даже несмотря на то, что в системном словаре программы 106 тысяч слов в базовой форме. Следовательно, как бы хороша база ни была, она все равно будет неполной. К счастью, словарь в моей программе САМЫЙ полный из всех известных мне программ-синонимайзеров. Все что нужно, это всего лишь правильно его организовать.
Качество базы стоит оценивать по тому, как посетители сайта относятся с таким “произведениям” и по тому, как охотно ПС кушают странички. Если т.н. bounce rate низок - это значит. что посетителям сайт нравится. Если же это значение подходит к 100%, значит ваш сайт может смело носить аббревиатуру ГС.
05.02.2009 в 09:54
А не знаешь случаем методик оценки качества корпусов текстов ?
05.02.2009 в 10:31
К сожалению я не знаю ни одной методики для оценки корпуса текстов. Этим вопросом занимается корпусная лингвистика, до которой я еще не дошел, так как это не было нужно в пределах выполняемых мною задач.
18.03.2009 в 05:15
Хорошая задумка, я за самый медленный и “правильный” вариант алгоритма.
А словарь пользователя от версии 0.4.1.1 теперь будет иметь другое значение?
18.03.2009 в 22:06
Не понимаю, что вы имеете в виду под другим значением словаря?
18.03.2009 в 23:24
В смысле, если он не подойдет к новой версии, превратиться в мусор
23.03.2009 в 09:29
Нет, как можно!? Он ведь в текстовом формате, и, следовательно, подойдет к любой версии программы.
03.05.2009 в 13:48
Было бы великолепно создавать свою собственную базу пар и в дальнейшем выбирать ее наряду со словарем. Это весьма полезно при обработке узкотематических текстов и также отчасти решает проблему определения контекста.
А по поводу выбора алгоритма. Можно реализовать несколько и позволить юзеру выбирать в настройках, например, скорость в ущерб корректности.
07.05.2009 в 14:52
Усё, заглохла разработка?
14.05.2009 в 09:13
2Wolf: как показал опыт, подобный функционал будет невостребован, так как народ не хочет работать ни руками, ни головой, предпочитая находить готовые словари. Поэтому я вряд ли решусь на такой шаг.
2Вадим: нет, разработка не заглохла. Просто в настоящий момент появилось достаточно много работы, которую нужно выполнить более срочно.
25.05.2009 в 13:21
Насчёт пары слов , это действително будет неостребованно большинством людей, хотя кого-то возможно и заинтересует.
Есть пару других замечаний.
Словарь очень часто не изменияет слова(всмысле оставляет слово в базовой форме).
Чаще всего это происходит с глаголами. Когда, например в тексте появляется вместо “мальчик ходил” - “мальчик ходить” ,это нехорошо.
Повторю, это косяк проскакивает очень и очень часто.
К тому же мои попытки добавить слово в нужной форме ни к чему не привели так, как словарь всё равно преобразует слово в базовую форму.
Над этим стоит задуматься.
Ещё одно пожелание.
Не стоит заменять большинство предлогов и такие слова ,как “было,как,что и т.д.” .Так как зачастую правильно заменить их невозможно, лучше немного поработать над словарём(на - пользователям) и добиться увеличения кол-ва замен, увеличением словарного запаса.
25.05.2009 в 16:50
Интересно, а как Вы наполняли таблицы комбинаций частей речи?
Ведь надо как-то определить связанность определенных слов.
Т.е. вот например текст:
> Как вы понимаете, разбиение на пары по частям речи нужно для того, чтобы значительно уменьшить время поиска.
Анализируя его нужно в таблицу поместить комбинации:
разбиение на пары
частям речи
значительно уменьшить
время поиска
и при этом отбросить весь остальной мусор
при этом не добавив:
понимаете разбиение
пары по частям
речи нужно
чтобы значительно
и т.д.
28.05.2009 в 09:18
2Vitalino: новая версия программы будет полностью переработана. Это будет значить, что большинство косяков из программы уйдут.
2Evgen: Под разбиением на пары по частям речи я подразумевал ПРЕДОПРЕДЕЛЕННЫЕ пары частей речи. Так как программа разбирается с частями речи (проблема пока что с омонимами, но она тоже решаема), то понять, что определенное слово представляет собой определенную часть речи, не составляет труда. Таким образом указанный вами мусор будет отброшен, так как
“пары по частям” - aж три слова, среди которых находится предлог,
“речи нужно” и “чтобы значительно” - содержат наречие, а его мы не учитываем,
единственная пара, которая в мусор не попадет, будет “понимаете разбиение” - представляющая собой пару “глагол-существительное”. Правда, так как словарь содержит только статистическую информацию, то такая пара слов в нем скорее всего будет отсутствовать.
24.07.2009 в 18:08
когда же выйдет новая версия программы? уже столько ждем…