Эта тема на forum.dklab.ru


phalanxx: Алгоритм сравнения текстов
В общем, имеется задача - сравнить несколько текстов на предмет их схожести. можно ли численно определить степень схожести двух текстов?
Ksnk:
Если тексты - строчные - можно завести массив хешей строк и потом пытаться сравнивать массивы получившихся чисел. Эти хеши можно считать с разными вывертами, учитывая case-sencitive+white-space'ы разные.
В самом тупом случае - сравниваем 2 массива
1 бежим до первого несравнения хешей,
2 из первого массива берем значение и ищем во втором такой-же,
2.1 если следующие совпали - проверяем строки на реальное совпадение с учетом вывертов... - начинаем отсюда пункт 1.
2.2 если следующие не совпали - бежим дальше по второму массиву до конца
2.3 если добежали до конца второго массива - берем вторую строчку первого и по новой (2)...

Кстати - можно поискать более разумные алгоритмы сравнения массивов...
phalanxx:
Да, но применительно к русскому языку это работать не будет: если в первом тексте есть слово "синхрофазотронный", а во втором - "синхрофазотрон", то хеши не совпадут. К тому же тексты будут браться с разных сайтов (работаем над подборкой новостей по типу news.yandex.ru), а у них различается дизайн... В результате хеши строк, различных по длине, опять не совпадут. Может лучше хешировать слова?
Я слышал о "методе шинглов", может кто знает в чем он состоит?
Ksnk:
Мне даже сложно что-то на такое возразить :) А как себе представлется сравнение , учитывающее разнописание одного слова?

Или речь идет о "смысловой" похожести текстов, а не реального совпадения контента?

Для смысла можно предложить "выделять корень слова" (где-то тут была какая-то веточка про это), считать количество одинаковых корней. Да! Слова нужно брать подлиннее :). Брать несколько самых встречающихся корней слов и сравниват уже эти массивы. Естественно, по совпадению вообще...
phalanxx:
А как себе представлется сравнение , учитывающее разнописание одного слова?
Для смысла можно предложить "выделять корень слова" (где-то тут была какая-то веточка про это), считать количество одинаковых корней.
Ну да. Надо выделить корень, только не во всех словах, а исключить всякие предлоги и союзы из текста.

Или речь идет о "смысловой" похожести текстов, а не реального совпадения контента?
Ну не совсем так - нужно сравнить все тексты из базы. Те, которые можно считать идентичными - не публиковать все, а привести один. Остальные (те, которые совпали) - удалить. Те, которые не совпали - сравнить исключив первый и т.д. Очевидно, что нужно вводить какие-то коэффициенты, главная проблема - определить их.
Ant:
Ну да. Надо выделить корень, только не во всех словах, а исключить всякие предлоги и союзы из текста.
Ну так выбрасывайте всё, что меньше 3-4-х букв. У остальных выделяйте корни (как это делается — ищите в складе готовых решений на этом форуме).
Anonymous:
Ну да. Надо выделить корень, только не во всех словах, а исключить всякие предлоги и союзы из текста.
Ну так выбрасывайте всё, что меньше 3-4-х букв. У остальных выделяйте корни (как это делается — ищите в складе готовых решений на этом форуме).

Это-то в принципе понятно. Я просто думал, может кто знает какие-либо другие решения - морфологией заниматься не очень хочется =(. Основная проблемы - определение коэффициентов, о которых я писал выше.
Ant:
Явно в такими алгоритмами я лично не работал, поэтому точно сказать не смогу. С другой стороны, можете посмотреть в сторону Wiki (на которой основан наш FAQ: http://faq.dklab.ru/Glavnaja). Там есть сравнение текстов (по какому-то алгоритму — названия не помню). По тому же алгоритму (вроде бы, не помню точно) работает сравнение версий в базе знаний XpW (http://xpoint.ru/know-how/). Если хотите, можете поискать там (на самом форуме и в базе).
Иван Шумков:
Ant
Сравниваются версии совершенно по другому алгоритму.
az:
Для сранения двух слов можно использовать встроенную в php функцию similar_text. Например:

<?php
$word1 = "синхрофазотронный";
$word2 = "синхрофазотрон";
$percent = 0;
$result = similar_text ($word1, $word2, $percent);
echo "Степень схожести слов $word1, $word2, $percent%";
?>

Выдаст: Степень схожести слов синхрофазотронный, синхрофазотрон, 90.3225806452%

Дополнительную информацию по данной теме, если интересует именно теоретическая часть, можно получить здесь: http://itman.narod.ru/ir/faq/fzfaq_calc.html. После прочтения, рекомендую еще ознакомиться со следующими функциями php, как:
levenshtein(), metaphone() и soundex().
Дамир Хуснатдинов:
Если дело все-таки дойдет до морфологии, то есть такая хорошая вещь - ispell: http://xpoint.ru/know-how/VebAlgoritmyi/RabotaSTekstami/RabotaSRusskoyMorfologieyPriPomoschiSlovaryaIspell
phalanxx:
Дело в том, что пока неизвестно, на чем будет реализована система - на PHP или на C++. Я потому и спрашиваю имеено алгоритм, функции я сам могу в мануале посмотреть. Но все равно спасибо за ссылки.
phprus:
Я слышал о "методе шинглов", может кто знает в чем он состоит?
Про метод Шинглов можно почитать тут - http://company.yandex.ru/articles/antispam.xml
Дивинский Артем:
Я сделал такую систему достаточно давно, то есть то, что я пишу не предположения о том как это можно было бы сделать, а вариант, который реально работает.
Но это не так то просто описать, всё времени не хватает написать статью, а в двух словах этого не расскажешь, так что, извините, могу задать Вам только общее направление.

Если Вы хотите знать насколько два документа схожи по смыслу:

Используеться пространственно-векторное представление текста по базису из лемм(ну по сути текст - это вектор в, приблизительно, двустатысячимерном :) пространстве осями которого являються леммы русского языка)
Итак
1 морфология
в простом варианте хотя бы таблица словоформ для лемм русского(в данном случае) языка (ispell не советую, даже "ветер" и "ветра" там разные леммы)
2 индексация текстов в виде лемма=частота в конкретном тексте, для всех лемм инверсная частота, для всех текстов скалярные длины их векторов
3 для вычисления "похожести" текстов достаточно вычислить косинус угла между ними (Аналитическую геометрию не забыли еще :) )
чем ближе косинус к единице, тем, естественно документы более схожи по смыслу
результат "1" получим при сравнении документа с самим собой
SelenIT:
Дивинский Артем
Уточните, пожалуйста, верно ли я понял, что Ваш подход учитывает только частоту слов (лемм) в текстах, но не их последовательность?
Дивинский Артем:
SelenIT

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

Детали функционирования всего этого в двух словах объяснить у меня не получиться. Если Вас интересует эта тема сходите, пожалуйста, в Google, например (лучше англоязычный).

Скажу только что в том виде в котором я это описал, схема представляет собой классическую теорию. Обычно в неё добавляют "специй по вкусу" при написании реальных приложений.
У меня она используеться для поиска по сайтам. Индексируется запрос(фраза), затем из коллекции документов выбираються похожие(документы). При поиске похожих документов - принцип тот же.
К примеру, на сайте спортивной команды при поиске по фамилии игрока - получим его резюме, при поиске док-тов похожих на резюме - получим резюме всех остальных игроков, при поиске док-тов похожих на календарь игр за январь - получим календари за все остальные месяцы, затем суммарные по годам и т. д.
Естественно, для того, чтобы все функционировало как описано пришлось многое "надстроить" над классикой, но эти "надстройки" в основном касались получения выгоды из того, что мы анализируем HTML, а не обычный текст.
html:
предлагаю теме дать большую оценку, в связи с высокой актуальностью решаемой проблемы .....
Ramzes:
Дивинский Артем
Шикарная система, только я вот не очень понял каким это таким интересным образом вы находите косинус угла между двумя векторами, может я плохо помню аналитическую геометрию, но для того, чтоб найти косинус угла между векторами, надо поделить векторное произведение векторов, на их скалярное произведение, в связи с чем у меня возник вопрос:
Вы маньяк?!!! Если еще скалярное произведение хоть как-то терпимо, то я совсем не могу понять, как вы считаете векторное произведение в таком охрененном базисе?!! Если вы считаете по другой формуле, то скажите ее плиз, а то мне немного плоховато уже стало...
Дмитрий Котеров:
для того, чтоб найти косинус угла между векторами, надо поделить векторное произведение векторов, на их скалярное произведение
Хм... Векторное произведение - вектор. Скалярное произведение - скаляр. Вектор делить на скаляр - вектор. Косинус - скаляр. Так, что, похоже,
может я плохо помню аналитическую геометрию
Артeм Дивинcкий:
Вы маньяк?!!!

Если исходить из предположения, что каждый исследуемый текст имеет ненулевые координаты по всем осям базиса - то да. Но так как я еще никогда не встречал текст, который бы содержал все леммы языка (если не брать в расчет теоретический случай - Большой Энциклопедический Словарь в одном файле (-; ) - то нет. (-:

А что касается формулы:
1 Косинус угла между векторами равен скалярному произведению векторов делённому на произведение длин векторов.
2 Длины просчитываются на этапе индексации.
3 X * 0 = 0 поэтому при вычислении скалярного произведения операций умножения столько, сколько лемм встречаются в обоих сравниваемых текстах, и размерность базиса не имеет значения.
Артeм Дивинcкий:
G. Salton. Automatic Text Processing. Addison-Wesley Publishing Company, Inc., Reading, MA, 1989.

Теоретически в ней должно быть все, что нужно. (Самому, к сожалению, читать не доводилось, так что ручаться не могу).
zaartix:
могу выложить архивчик с очень большим количеством исходных форм и словоформ каждой из них. Правда придется распарсить предварительно словоформы, т.к. они сохранены в виде хтмл в таблице.
вот один из примеров по исходной форме:

<title>Морфологический анализ</title>
<meta http-equiv="Content-Type" content="text/html; charset=cp1251">
<body bgcolor="#ffffff" text="#000000" link="blue" vlink="purple" alink="red" >
<br>
Исходная форма: абсорбировать<p>Словарная информация: св-нсв 2а <p> Перевод: <A HREF="morph.cgi?flags=wndnnnn&word=absorb||[absorbirovat'">absorb</A>; <A HREF="morph.cgi?flags=wndnnnn&word=absorptive||[absorbirovat'">absorptive</A>; <A HREF="morph.cgi?flags=wndnnnn&word=absorptivity||[absorbirovat'">absorptivity</A>;<p>Морфологическая характеристика: pass. inf.<p><p><hr>
<br>
<b>Инфинитив:</b> абсорби'ровать
<h2>Действительный залог</h2>
<h3>Настояще-будущее время</h3>
<table border=1>
<tr>
<th align=left></th>
<th align=left>Ед. число</th>
<th align=left>Множ. число</th>
</tr>
<tr>
<th align=left>1 лицо</th>
<td align=left>абсорби'рую</td>
<td align=left>абсорби'руем</td>
</tr>
<tr>
<th align=left>2 лицо</th>
<td align=left>абсорби'руешь</td>
<td align=left>абсорби'руете</td>
</tr>
<tr>
<th align=left>3 лицо</th>
<td align=left>абсорби'рует</td>
<td align=left>абсорби'руют</td>
</tr>
</table>
<br>
<br>
<b>Деепричастие:</b> абсорби'руя
<h3>Прошедшее время</h3>
<table border=1>
<tr>
<th align=left>Мужской</th>
<th align=left>Женский</th>
<th align=left>Средний</th>
<th align=left>Множ. число</th>
</tr>
<tr>
<td align=left>абсорби'ровал</td>
<td align=left>абсорби'ровала</td>
<td align=left>абсорби'ровало</td>
<td align=left>абсорби'ровали</td>
</tr>
</table>
<br>

<br>
<br>
<b>Деепричастие:</b> абсорби'ровавши//абсорби'ровав
<h3>Повелительное наклонение</h3>
<table border=1>
<tr>
<th align=left>Ед. число</th>
<th align=left>Множ. число</th>
</tr>
<tr>
<td align=left>абсорби'руй</td>
<td align=left>абсорби'руйте</td>
</tr>
</table>
<br>
<h3>Причастие настоящего времени</h3>
<table border=1>
<tr>
<th align=left></th>
<th align=left>Мужской</th>
<th align=left>Женский</th>
<th align=left>Средний</th>
<th align=left>Множ. число</th>
</tr>
<tr>
<th align=left>Именительный</th>
<td align=left>абсорби'рующий</td>
<td align=left>абсорби'рующая</td>
<td align=left>абсорби'рующее</td>
<td align=left>абсорби'рующие</td>
</tr>
<tr>
<th align=left>Родительный</th>
<td align=left>абсорби'рующего</td>
<td align=left>абсорби'рующей</td>
<td align=left>абсорби'рующего</td>
<td align=left>абсорби'рующих</td>
</tr>
<tr>
<th align=left>Дательный</th>
<td align=left>абсорби'рующему</td>
<td align=left>абсорби'рующей</td>
<td align=left>абсорби'рующему</td>
<td align=left>абсорби'рующим</td>
</tr>
<tr>
<th align=left>Винительный неод.</th>
<td align=left>абсорби'рующий</td>
<td align=left>абсорби'рующую</td>
<td align=left>абсорби'рующее</td>
<td align=left>абсорби'рующие</td>
</tr>
<tr>
<th align=left>Винительный одуш.</th>
<td align=left>абсорби'рующего</td>
<td align=left>абсорби'рующую</td>
<td align=left>абсорби'рующее</td>
<td align=left>абсорби'рующих</td>
</tr>
<tr>
<th align=left>Творительный</th>
<td align=left>абсорби'рующим</td>
<td align=left>абсорби'рующей, абсорби'рующею</td>
<td align=left>абсорби'рующим</td>
<td align=left>абсорби'рующими</td>
</tr>
<tr>
<th align=left>Предложный</th>
<td align=left>абсорби'рующем</td>
<td align=left>абсорби'рующей</td>
<td align=left>абсорби'рующем</td>
<td align=left>абсорби'рующих</td>
</tr>
</table>
<h3>Причастие прошедшего времени</h3>
<table border=1>
<tr>
<th align=left></th>
<th align=left>Мужской</th>
<th align=left>Женский</th>
<th align=left>Средний</th>
<th align=left>Множ. число</th>
</tr>
<tr>
<th align=left>Именительный</th>
<td align=left>абсорби'ровавший</td>
<td align=left>абсорби'ровавшая</td>
<td align=left>абсорби'ровавшее</td>
<td align=left>абсорби'ровавшие</td>
</tr>
<tr>
<th align=left>Родительный</th>
<td align=left>абсорби'ровавшего</td>
<td align=left>абсорби'ровавшей</td>
<td align=left>абсорби'ровавшего</td>
<td align=left>абсорби'ровавших</td>
</tr>
<tr>
<th align=left>Дательный</th>
<td align=left>абсорби'ровавшему</td>
<td align=left>абсорби'ровавшей</td>
<td align=left>абсорби'ровавшему</td>
<td align=left>абсорби'ровавшим</td>
</tr>
<tr>
<th align=left>Винительный неод.</th>
<td align=left>абсорби'ровавший</td>
<td align=left>абсорби'ровавшую</td>
<td align=left>абсорби'ровавшее</td>
<td align=left>абсорби'ровавшие</td>
</tr>
<tr>
<th align=left>Винительный одуш.</th>
<td align=left>абсорби'ровавшего</td>
<td align=left>абсорби'ровавшую</td>
<td align=left>абсорби'ровавшее</td>
<td align=left>абсорби'ровавших</td>
</tr>
<tr>
<th align=left>Творительный</th>
<td align=left>абсорби'ровавшим</td>
<td align=left>абсорби'ровавшей, абсорби'ровавшею</td>
<td align=left>абсорби'ровавшим</td>
<td align=left>абсорби'ровавшими</td>
</tr>
<tr>
<th align=left>Предложный</th>
<td align=left>абсорби'ровавшем</td>
<td align=left>абсорби'ровавшей</td>
<td align=left>абсорби'ровавшем</td>
<td align=left>абсорби'ровавших</td>
</tr>
</table>
<h2>Страдательный залог</h2>
<h3>Настояще-будущее время</h3>
<table border=1>
<tr>
<th align=left></th>
<th align=left>Ед. число</th>
<th align=left>Множ. число</th>
</tr>
<tr>
<th align=left>1 лицо</th>
<td align=left>абсорби'руюсь</td>
<td align=left>абсорби'руемся</td>
</tr>
<tr>
<th align=left>2 лицо</th>
<td align=left>абсорби'руешься</td>
<td align=left>абсорби'руетесь</td>
</tr>
<tr>
<th align=left>3 лицо</th>
<td align=left>абсорби'руется</td>
<td align=left>абсорби'руются</td>
</tr>
</table>
<br>
<h3>Прошедшее время</h3>
<table border=1>
<tr>
<th align=left>Мужской</th>
<th align=left>Женский</th>
<th align=left>Средний</th>
<th align=left>Множ. число</th>
</tr>
<tr>
<td align=left>абсорби'ровался</td>
<td align=left>абсорби'ровалась</td>
<td align=left>абсорби'ровалось</td>
<td align=left>абсорби'ровались</td>
</tr>
</table>
<br>

<br>
<h3>Повелительное наклонение</h3>
<table border=1>
<tr>
<th align=left>Ед. число</th>
<th align=left>Множ. число</th>
</tr>
<tr>
<td align=left>абсорби'руйся</td>
<td align=left>абсорби'руйтесь</td>
</tr>
</table>
<br>
<h3>Причастие настоящего времени</h3>
<table border=1>
<tr>
<th align=left></th>
<th align=left>Мужской</th>
<th align=left>Женский</th>
<th align=left>Средний</th>
<th align=left>Множ. число</th>
</tr>
<tr>
<th align=left>Именительный</th>
<td align=left>абсорби'руемый, абсорби'рующийся</td>
<td align=left>абсорби'руемая, абсорби'рующаяся</td>
<td align=left>абсорби'руемое, абсорби'рующееся</td>
<td align=left>абсорби'руемые, абсорби'рующиеся</td>
</tr>
<tr>
<th align=left>Родительный</th>
<td align=left>абсорби'руемого, абсорби'рующегося</td>
<td align=left>абсорби'руемой, абсорби'рующейся</td>
<td align=left>абсорби'руемого, абсорби'рующегося</td>
<td align=left>абсорби'руемых, абсорби'рующихся</td>
</tr>
<tr>
<th align=left>Дательный</th>
<td align=left>абсорби'руемому, абсорби'рующемуся</td>
<td align=left>абсорби'руемой, абсорби'рующейся</td>
<td align=left>абсорби'руемому, абсорби'рующемуся</td>
<td align=left>абсорби'руемым, абсорби'рующимся</td>
</tr>
<tr>
<th align=left>Винительный неод.</th>
<td align=left>абсорби'руемый, абсорби'рующийся</td>
<td align=left>абсорби'руемую, абсорби'рующуюся</td>
<td align=left>абсорби'руемое, абсорби'рующееся</td>
<td align=left>абсорби'руемые, абсорби'рующиеся</td>
</tr>
<tr>
<th align=left>Винительный одуш.</th>
<td align=left>абсорби'руемого, абсорби'рующегося</td>
<td align=left>абсорби'руемую, абсорби'рующуюся</td>
<td align=left>абсорби'руемое, абсорби'рующееся</td>
<td align=left>абсорби'руемых, абсорби'рующихся</td>
</tr>
<tr>
<th align=left>Творительный</th>
<td align=left>абсорби'руемым, абсорби'рующимся</td>
<td align=left>абсорби'руемой, абсорби'руемою, абсорби'рующейся, абсорби'рующеюся</td>
<td align=left>абсорби'руемым, абсорби'рующимся</td>
<td align=left>абсорби'руемыми, абсорби'рующимися</td>
</tr>
<tr>
<th align=left>Предложный</th>
<td align=left>абсорби'руемом, абсорби'рующемся</td>
<td align=left>абсорби'руемой, абсорби'рующейся</td>
<td align=left>абсорби'руемом, абсорби'рующемся</td>
<td align=left>абсорби'руемых, абсорби'рующихся</td>
</tr>
<tr>
<th align=left>Краткая форма</th>
<td align=left>абсорби'руем</td>
<td align=left>абсорби'руема</td>
<td align=left>абсорби'руемо</td>
<td align=left>абсорби'руемы</td>
</tr>
</table>
<h3>Причастие прошедшего времени</h3>
<table border=1>
<tr>
<th align=left></th>
<th align=left>Мужской</th>
<th align=left>Женский</th>
<th align=left>Средний</th>
<th align=left>Множ. число</th>
</tr>
<tr>
<th align=left>Именительный</th>
<td align=left>абсорби'рованный</td>
<td align=left>абсорби'рованная</td>
<td align=left>абсорби'рованное</td>
<td align=left>абсорби'рованные</td>
</tr>
<tr>
<th align=left>Родительный</th>
<td align=left>абсорби'рованного</td>
<td align=left>абсорби'рованной</td>
<td align=left>абсорби'рованного</td>
<td align=left>абсорби'рованных</td>
</tr>
<tr>
<th align=left>Дательный</th>
<td align=left>абсорби'рованному</td>
<td align=left>абсорби'рованной</td>
<td align=left>абсорби'рованному</td>
<td align=left>абсорби'рованным</td>
</tr>
<tr>
<th align=left>Винительный неод.</th>
<td align=left>абсорби'рованный</td>
<td align=left>абсорби'рованную</td>
<td align=left>абсорби'рованное</td>
<td align=left>абсорби'рованные</td>
</tr>
<tr>
<th align=left>Винительный одуш.</th>
<td align=left>абсорби'рованного</td>
<td align=left>абсорби'рованную</td>
<td align=left>абсорби'рованное</td>
<td align=left>абсорби'рованных</td>
</tr>
<tr>
<th align=left>Творительный</th>
<td align=left>абсорби'рованным</td>
<td align=left>абсорби'рованной, абсорби'рованною</td>
<td align=left>абсорби'рованным</td>
<td align=left>абсорби'рованными</td>
</tr>
<tr>
<th align=left>Предложный</th>
<td align=left>абсорби'рованном</td>
<td align=left>абсорби'рованной</td>
<td align=left>абсорби'рованном</td>
<td align=left>абсорби'рованных</td>
</tr>
<tr>
<th align=left>Краткая форма</th>
<td align=left>абсорби'рован</td>
<td align=left>абсорби'рована</td>
<td align=left>абсорби'ровано</td>
<td align=left>абсорби'рованы</td>
</tr>
</table>
<hr>
</body>

sbrv:
zaartix "могу выложить архивчик с очень большим количеством исходных форм и словоформ каждой из них."

если не сложно вышли на sbrv@yandex.ru
dkrnl:
zaartix можно на dkrnl@yandex.ru, а лучше на фтп какойнить.
спасибо.
phprus:
zaartix
Отправь мне пожалуйста этот архив на email phprus@gmail.com
Maus:
zaartix
Почему бы Вам не выложить этот файл здесь, аттачем?
Sla_sh:
люди, подскажите, где можно взять такого рода архив пожалуйста.
мне очень срочно нужно...
Stan:


А что касается формулы:
1 Косинус угла между векторами равен скалярному произведению векторов делённому на произведение длин векторов.
2 Длины просчитываются на этапе индексации.
3 X * 0 = 0 поэтому при вычислении скалярного произведения операций умножения столько, сколько лемм встречаются в обоих сравниваемых текстах, и размерность базиса не имеет значения.

Если дано:
Текст 1, содержащий слова с корнями a,b,c в количестве, соответственно, a1,b1,c1
текст 2 — с корнями a, b, d в количестве: a2,b2,d2 — соответствующее количество этих корней то:
Скалярное произведение векторов равно: a1*a2 + b1*b2
Произведение длин векторов: sqrt(a1*a1+b1*b1+c1*c1)*sqrt(a2*a2+b2*b2+d2*d2)

Скажите, пожалуйста, это правильно?
Anonymous:
Выше упоминался скрипт выделения корней из русского слова:
Ну да. Надо выделить корень, только не во всех словах, а исключить всякие предлоги и союзы из текста.
Ну так выбрасывайте всё, что меньше 3-4-х букв. У остальных выделяйте корни (как это делается — ищите в складе готовых решений на этом форуме).

Вот ссылка:
http://forum.dklab.ru/php/advises/HeuristicWithoutTheDictionaryExtractionOfARootFromRussianWord.html
Eric-S:
Немного сменю направление мысли относительно сравнения. Не большой текст, а просто строчка, нужно найтив бд нужную запись.

Я тут вчера писал одну функцию для поиска по базе данных имён авторов. Потому, что я пришел к выводу, что стандартные методики не выводят всех нужных, а хеширование опять же не помогает. Вот например в базе имя "Артём", а я ищу "артем" — фиг что нашел! А если ещё добавить проблему некорректного или даже ошибочного ввода, то тут найти ещё сложнее.

Проблема оказалась относительно неплохо решаема. Если привести слова к стандартному виду (хранить в отдельном столбце, вместо хэша), и искать именно этот стандартный вид, то даже меня результаты потрясли.

Вот посмотрите,всё очень просто.


function tcompress($string) { /*
сжатие и приведение текста к одному стандарту (только для сравнения, двух строк!)
на выходе латинизированный текст.Без повторяющихся букв.
*/

// в нижний регистр
$line = strtolower($string);

// удаляем повторные символы
$string = ""; $o = "";
for ($i = 0; $i < strlen($line); $i++) {
$c = substr($line, $i, 1);
if ($c != $o) {
$string .= $c;
$o = $c;
} }

// исправляем буквосочетания
$rus=array(' - ','-','tc','yo','jo','ju','ja','sch','эй','ай','дж','кс','ку','зт','вв','ж','ц','ч','ш','щ','ю','я','ъ','ь');
$lat=array(' — ','–','ts','e','e','yu','ya','sh','a','i','j','x','q','z','w','zh','ts','ch','sh','sh','yu','ya','','');
$string=str_replace($rus,$lat,$string);

// транслируем символы
$string=strtr($string,
"0123456789pshwабвгдеёзийклмнопрстуфхыэ",
"oigzq5bg8jpcxvabvgdeeziiklmhoppctufxie");

return($string); }


Что вы об этом думаете? Может быть я подошел к этой проблемме совсем не стой стороны, и где нибудь заблуждаюсь?
Функция пока ещё не прошла полевых испытаний и возможно требует некоторых дополнений.

Возвращаясь обратно к теме, хочу заметить, что различные методики не всегда дадут 100% результат. Возможно нужно комбинировать их.

Недавно тут читал про поисково индексирующий алгоритм. Как выше уже упоминалось используется векторное представление документа, но ведь можно и проще. Например сравнить слова с большим весом и рейтингом. Тут кстати будет и автоматическая фильтрация незначащих (мусорных) слов.
Blagotvor:
алгоритмы алгоритмами... но может быть все же есть у кого ни будь готовая функция сравнения на PHP? мне необходимо сделать проверку входящего текста с уже имеющимся в базе, чтобы исключать повторы или сильные совпадения.
Anonymous:
<pre><?
define('SHINGLEBOX_FUNC_NUM', 100);
define('SHINGLEBOX_SNIPPET_LENGTH_DEF', 6);

class ShingleBox {
var $permuts = array();
var $snippetLength;

function ShingleBox($snipLength = SHINGLEBOX_SNIPPET_LENGTH_DEF) {
$this->snippetLength = $snipLength;
$this->_init_permuts();
}
function _init_permuts() {
$registrator = array();
$permutation = array();
for ($i = 0; $i < $this->snippetLength; $i++)
$permutation[$i] = $i;
for ($i = 0; $i < SHINGLEBOX_FUNC_NUM; $i++) {
while(isset($registrator))
for ($j = rand(77,111); $j > 0; $j--)
array_swap($permutation);
$registrator = $permutation)] = 1;
}
}

function giveShingles(&$words){
$snippets = array();
for ($i = 0; $i <= count($words)-$this->snippetLength || $i == 0; $i++)
$snippets[] = array_slice($words, $i, $this->snippetLength);
while(count($snippets[0]) < $this->snippetLength)
$snippets[0][] = rand(0,999999);
$shingles = array();
foreach ($this->permuts as $fi => $permut) {
foreach ($snippets as $i => $snip) {
$hash = md5(implode(':', array_permutation($snip, $permut)));
$sh = ($i == 0 || strcmp($hash,$sh) < 0)? $hash : $sh;
}
$shingles[] = $sh;
}
return array_slice($shingles, 0, 36);
}
function giveSuper($words, $superCount) {
$sh = $this->giveShingles($words);
$i = 1; $shingles = null;
foreach ($sh as $value){
if ($i == 6){
$supersh[] = md5($shingles);
$shingles = null;
$i = 1;
} else $shingles .= $value;
$i++;
}
return $supersh;
}
}

function array_swap(&$a, $i1=-1, $i2=-1) {
$i1 = $i1==-1? rand(0, count($a)-1) : $i1;
$i2 = $i2==-1? rand(0, count($a)-1) : $i2;
$t = $a[$i1];
$a[$i1] = $a[$i2];
$a[$i2] = $t;
}
function array_permutation(&$array, &$permut) {
$result = array();
foreach ($permut as $to => $from)
$result[$to] = $array[$from];
return $result;
}

function permutations_cmp($p1, $p2) {
return strcmp(implode('', $p1), implode('', $p2));
}
?>


<?require_once 'lib.php';
$shingleBox = new ShingleBox;

foreach (array(0, 1) as $i)
$shingles[$i] = $shingleBox->giveSuper(getWords($_REQUEST['text'][$i]), 9);

foreach (array(0, 1) as $i) {
$cont = array();
foreach ($shingles[$i] as $shi => $sh)
$cont[] = in_array($sh, $shingles[1-$i])? "<b>$sh</b>" : "$sh";
$_REQUEST['text'][$i] = implode("\n", $cont);
}
$eqCount = 0;

print_r($shingles);

for ($i = 0; $i < 6; $i++)
if ($shingles[0][$i] == $shingles[1][$i]) $eqCount++;
$report = sprintf("%01.2f%%", 100*$eqCount/6);

echo $eqCount;

// похожесть перестановок
$eqCount = 0;
$p =& $shingleBox->permuts;
for ($i = 0; $i < SHINGLEBOX_FUNC_NUM; $i++)
for ($j = 0; $j < SHINGLEBOX_FUNC_NUM; $j++)
for ($k = 0; $k < SHINGLEBOX_SNIPPET_LENGTH_DEF; $k++)
if ($p[$i][$k] == $p[$j][$k]) $eqCount++;

// список перестановок
$a = array();
foreach ($shingleBox->permuts as $prem)
$a[] = implode('', $prem)."\n";
sort($a);

require_once "FormPersister.php";
$HTML_FormPersister = new HTML_FormPersister();
print $HTML_FormPersister->process("
<table style='width:100%;height=100%;'><tr>
<form action='' method='post'>
<td width='44%' valign='top'>
<textarea name='text[0]' rows=23 style='width:100%;height=100%;'></textarea>
<pre style='font-size:11px'>{$_REQUEST['text'][0]}</pre>
</td>
<td valign='top'>
<input type='submit' value='send'>
<pre>$report</pre>
</td>
<td width='44%' valign='top'>
<textarea name='text[1]' rows=23 style='width:100%;height=100%;'></textarea>
<pre style='font-size:11px'>{$_REQUEST['text'][1]}</pre>
</td>
</form>
</tr></table>
");

function getWords($sen) {
preg_match_all('|{3,99}|i', $sen, $m);
return $m[0];
}
?>

Но проблема в том что я не знаю как нормировать длинну документа, с супер шинглами понятно все - они то и позволяют найти нечеткие дубли, но мне нужно еще знать и не только процент подобия документа но и места совпадений, а как нормировать длинну шинглов я незнаю, предполагаю что нужно брать самый длинный и по нему делать цикл
leosun:
Ну и итоговый ответ я думаю, вот


<?
$text_1 = isset($_REQUEST['text_1']) ? $_REQUEST['text_1'] : null;
$text_2 = isset($_REQUEST['text_2']) ? $_REQUEST['text_2'] : null;

if (!empty($text_1) && !empty($text_2)){
if (strlen($text_1) >= strlen($text_2)){
$big = explode(' ',$text_1);
$small = explode(' ',$text_2);
$big_text = $text_1;
$small_text = $text_2;
} else {
$small = explode(' ',$text_1);
$big = explode(' ',$text_2);
$big_text = $text_2;
$small_text = $text_1;
}

$l = count($big);
for($i=0;$i<$l-2;$i++) {
$sh['big'].' '.$big[$i+1].' '.$big[$i+2],' '))] = $big[$i].' '.$big[$i+1].' '.$big[$i+2];
}

$l = count($small);
for($i=0;$i<$l-2;$i++) {
$sh['small'].' '.$small[$i+1].' '.$small[$i+2],' '))] = $small[$i].' '.$small[$i+1].' '.$small[$i+2];
}

foreach ($sh['big'] as $sh_big_key => $sh_big){
$j = 0;
foreach ($sh['small'] as $sh_small_key => $sh_small){
if ($sh_big_key == $sh_small_key){
$j = 1;
$all_small[$sh_small_key] = '<b>'.$sh_small_key.'</b>';
} else {
if ($all_small[$sh_small_key] != '<b>'.$sh_small_key.'</b>')
$all_small[$sh_small_key] = $sh_small_key;
}
}
if ($j == 1)
$all_big[] = '<b>'.$sh_big_key.'</b>';
else
$all_big[] = $sh_big_key;
}
echo '<table><tr valign="top">';
echo '<td>';
foreach ($all_big as $value){
echo $value.'<br>';
}
echo '</td>';
echo '<td>';
foreach ($all_small as $value){
echo $value.'<br>';
}
echo '</td>';
echo '</tr>';
echo '</table>';
}
?>
<form name="SendText" action="index.php" method="post">
<table width="100%">
<tr><td>
<b>Фрагмент - 1</b><br>
<textarea name="text_1" rows=20 cols=60 wrap="on"><?=$text_1?></textarea>
</td><td>
<b>Фрагмент - 2</b><br>
<textarea name="text_2" rows=20 cols=60 wrap="on"><?=$text_2?></textarea>
</td></tr><tr><td colspan="2">
<input type="submit" value="Сравнить">
</td></tr>
</table>
</form>

Evgensss:
могу выложить архивчик с очень большим количеством исходных форм и словоформ каждой из них.



Кто может, вышлите пожалуйста этот архив на Evgen@ksu.ks.ua
Tsvetkov:
алгоритмы алгоритмами... но может быть все же есть у кого ни будь готовая функция сравнения на PHP? мне необходимо сделать проверку входящего текста с уже имеющимся в базе, чтобы исключать повторы или сильные совпадения.

Вот, есть такое интересное решение: http://zendframework.ru/articles/zend-filter-keywords
Может кому будет полезно :)
Hunter Igor:
алгоритмы алгоритмами... но может быть все же есть у кого ни будь готовая функция сравнения на PHP? мне необходимо сделать проверку входящего текста с уже имеющимся в базе, чтобы исключать повторы или сильные совпадения.

function bd_is_string($str, $srow){
$out = 0;
$str1 = eregi_replace("[!,.:?;]", " ", $str);
$str1 = eregi_replace(" .{1,4} ", " ", $str1);
$str1 = eregi_replace(" +", " ", $str1);

$words = explode(' ', trim($str1));
$cnt = count($words);
$word_max = ceil($cnt/2);
$str1 = ""; $br=0;
foreach ($words as $word){ //считать 50% слов
$str1 .= " +$word";
$br++;
if ($br > $word_max) break;
}
$result = db_query("SELECT $srow FROM ".TABLENAME." WHERE MATCH($srow) AGAINST('$str1' IN BOOLEAN MODE)");
$rows = mysql_num_rows($result);
if ( $rows > 0) {
while($row = mysql_fetch_array($result)){
$str2 = eregi_replace("[!,.:?;]", " ", $row[$srow]);
$str2 = eregi_replace(" .{1,4} ", " ", $str2);
$str2 = eregi_replace(" +", " ", $str2);
$words2 = explode(' ', trim($str2));
$cnt2 = count($words2);
if ($cnt == $cnt2) $out = 1;
else {
if ($cnt < $cnt2) {
$perc=($cnt/100)*20;
$perc = ceil($perc);
if($cnt2-$cnt-$perc < 1 ) $out=1;
} else {
$perc=($cnt2/100)*20;
$perc = ceil($perc);
if($cnt-$cnt2-$perc < 1 ) $out=1;
}
if($out == false){

}
}
}
}
mysql_free_result($result);
if ($out == 0) {
return false;
}else{
return true;
}

}
Не оптимизировал - некогда, но оно работает.
dimagolov:
Hunter Igor, eregi_* is depreciated in php 5.3.x

Эта тема на forum.dklab.ru