Форум dkLab и Denwer

phalanxx · Guest Карма: 388 поощрить/наказать

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

Ksnk

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

Кстати - можно поискать более разумные алгоритмы сравнения массивов...

phalanxx · Guest Карма: 388 поощрить/наказать

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

Ksnk

Мне даже сложно что-то на такое возразить :) А как себе представлется сравнение , учитывающее разнописание одного слова?

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

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

phalanxx · Guest Карма: 388 поощрить/наказать

Ksnk wrote:

А как себе представлется сравнение , учитывающее разнописание одного слова?

Ksnk wrote:

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

Ну да. Надо выделить корень, только не во всех словах, а исключить всякие предлоги и союзы из текста.

Ksnk wrote:

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

Ну не совсем так - нужно сравнить все тексты из базы. Те, которые можно считать идентичными - не публиковать все, а привести один. Остальные (те, которые совпали) - удалить. Те, которые не совпали - сравнить исключив первый и т.д. Очевидно, что нужно вводить какие-то коэффициенты, главная проблема - определить их.

Ant

phalanxx wrote:

Ну да. Надо выделить корень, только не во всех словах, а исключить всякие предлоги и союзы из текста.

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

Guest · Карма: 388 поощрить/наказать

Ant wrote:

phalanxx wrote:

Ну да. Надо выделить корень, только не во всех словах, а исключить всякие предлоги и союзы из текста.

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

Это-то в принципе понятно. Я просто думал, может кто знает какие-либо другие решения - морфологией заниматься не очень хочется =(. Основная проблемы - определение коэффициентов, о которых я писал выше.

Ant

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

Иван Шумков

Ant
Сравниваются версии совершенно по другому алгоритму.

az

Для сранения двух слов можно использовать встроенную в php функцию similar_text. Например:

Code (php):	скопировать код в буфер обмена
<?php $word1 = "синхрофазотронный"; $word2 = "синхрофазотрон"; $percent = 0; $result = similar_text (www.php.net/similar_text) ($word1, $word2, $percent); echo (www.php.net/echo) "Степень схожести слов $word1, $word2, $percent%"; ?>

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

Дополнительную информацию по данной теме, если интересует именно теоретическая часть, можно получить здесь: itman.narod.ru/ir/faq/fzfaq_calc.html. После прочтения, рекомендую еще ознакомиться со следующими функциями php, как:

Code (php):	скопировать код в буфер обмена
levenshtein (www.php.net/levenshtein)(), metaphone (www.php.net/metaphone)() и soundex (www.php.net/soundex)().

Дамир Хуснатдинов

Если дело все-таки дойдет до морфологии, то есть такая хорошая вещь - ispell: xpoint.ru/know-how/VebAlgoritmyi/RabotaSTekstami/RabotaSRusskoyMorfologieyPriPomoschiSlovaryaIspell

phalanxx

Дело в том, что пока неизвестно, на чем будет реализована система - на PHP или на C++. Я потому и спрашиваю имеено алгоритм, функции я сам могу в мануале посмотреть. Но все равно спасибо за ссылки.

phprus

phalanxx wrote:

Я слышал о "методе шинглов", может кто знает в чем он состоит?

Про метод Шинглов можно почитать тут - company.yandex.ru/articles/antispam.xml

Дивинский Артем · Guest Карма: 388 поощрить/наказать

Я сделал такую систему достаточно давно, то есть то, что я пишу не предположения о том как это можно было бы сделать, а вариант, который реально работает.
Но это не так то просто описать, всё времени не хватает написать статью, а в двух словах этого не расскажешь, так что, извините, могу задать Вам только общее направление.

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

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

SelenIT

Дивинский Артем
Уточните, пожалуйста, верно ли я понял, что Ваш подход учитывает только частоту слов (лемм) в текстах, но не их последовательность?

Дивинский Артем · Guest Карма: 388 поощрить/наказать

SelenIT

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

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

Скажу только что в том виде в котором я это описал, схема представляет собой классическую теорию. Обычно в неё добавляют "специй по вкусу" при написании реальных приложений.
У меня она используеться для поиска по сайтам. Индексируется запрос(фраза), затем из коллекции документов выбираються похожие(документы). При поиске похожих документов - принцип тот же.
К примеру, на сайте спортивной команды при поиске по фамилии игрока - получим его резюме, при поиске док-тов похожих на резюме - получим резюме всех остальных игроков, при поиске док-тов похожих на календарь игр за январь - получим календари за все остальные месяцы, затем суммарные по годам и т. д.
Естественно, для того, чтобы все функционировало как описано пришлось многое "надстроить" над классикой, но эти "надстройки" в основном касались получения выгоды из того, что мы анализируем HTML, а не обычный текст.

html

предлагаю теме дать большую оценку, в связи с высокой актуальностью решаемой проблемы .....

Ramzes

Дивинский Артем
Шикарная система, только я вот не очень понял каким это таким интересным образом вы находите косинус угла между двумя векторами, может я плохо помню аналитическую геометрию, но для того, чтоб найти косинус угла между векторами, надо поделить векторное произведение векторов, на их скалярное произведение, в связи с чем у меня возник вопрос:
Вы маньяк?!!! Если еще скалярное произведение хоть как-то терпимо, то я совсем не могу понять, как вы считаете векторное произведение в таком охрененном базисе?!! Если вы считаете по другой формуле, то скажите ее плиз, а то мне немного плоховато уже стало...

Дмитрий Котеров

Ramzes wrote:

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

Хм... Векторное произведение - вектор. Скалярное произведение - скаляр. Вектор делить на скаляр - вектор. Косинус - скаляр. Так, что, похоже,

Ramzes wrote:

может я плохо помню аналитическую геометрию

Артeм Дивинcкий

Ramzes wrote:

Вы маньяк?!!!

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

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

Артeм Дивинcкий

G. Salton. Automatic Text Processing. Addison-Wesley Publishing Company, Inc., Reading, MA, 1989.

Теоретически в ней должно быть все, что нужно. (Самому, к сожалению, читать не доводилось, так что ручаться не могу).

zaartix

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

Code (html):

скопировать код в буфер обмена

<title> (december.com/html/4/element/title.html)</title>
<meta (december.com/html/4/element/meta.html) http-equiv="Content-Type" content="text/html; charset=cp1251"> (december.com/html/4/element/.html)
<body (december.com/html/4/element/body.html) bgcolor="#ffffff" text="#000000" link="blue" vlink="purple" alink="red" > (december.com/html/4/element/.html)
<br> (december.com/html/4/element/br.html)<p> (december.com/html/4/element/p.html)<p> (december.com/html/4/element/p.html)<A (december.com/html/4/element/a.html) HREF="morph.cgi?flags=wndnnnn&word=absorb||[absorbirovat'"> (december.com/html/4/element/.html)absorb</A>; <A (december.com/html/4/element/a.html) HREF="morph.cgi?flags=wndnnnn&word=absorptive||[absorbirovat'"> (december.com/html/4/element/.html)absorptive</A>; <A (december.com/html/4/element/a.html) HREF="morph.cgi?flags=wndnnnn&word=absorptivity||[absorbirovat'"> (december.com/html/4/element/.html)absorptivity</A>;<p> (december.com/html/4/element/p.html)<p> (december.com/html/4/element/p.html)<p> (december.com/html/4/element/p.html)<hr> (december.com/html/4/element/hr.html)
<br> (december.com/html/4/element/br.html)
<b> (december.com/html/4/element/b.html)</b><h2> (december.com/html/4/element/h2.html)</h2>
<h3> (december.com/html/4/element/h3.html)</h3>
<table (december.com/html/4/element/table.html) border=1>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<th (december.com/html/4/element/th.html) align=left></th>
<th (december.com/html/4/element/th.html) align=left></th>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
</table>
<br> (december.com/html/4/element/br.html)
<br> (december.com/html/4/element/br.html)
<b> (december.com/html/4/element/b.html)</b><h3> (december.com/html/4/element/h3.html)</h3>
<table (december.com/html/4/element/table.html) border=1>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<th (december.com/html/4/element/th.html) align=left></th>
<th (december.com/html/4/element/th.html) align=left></th>
<th (december.com/html/4/element/th.html) align=left></th>
</tr>
<tr> (december.com/html/4/element/tr.html)
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
</table>
<br> (december.com/html/4/element/br.html)

<br> (december.com/html/4/element/br.html)
<br> (december.com/html/4/element/br.html)
<b> (december.com/html/4/element/b.html)</b><h3> (december.com/html/4/element/h3.html)</h3>
<table (december.com/html/4/element/table.html) border=1>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<th (december.com/html/4/element/th.html) align=left></th>
</tr>
<tr> (december.com/html/4/element/tr.html)
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
</table>
<br> (december.com/html/4/element/br.html)
<h3> (december.com/html/4/element/h3.html)</h3>
<table (december.com/html/4/element/table.html) border=1>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<th (december.com/html/4/element/th.html) align=left></th>
<th (december.com/html/4/element/th.html) align=left></th>
<th (december.com/html/4/element/th.html) align=left></th>
<th (december.com/html/4/element/th.html) align=left></th>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
</table>
<h3> (december.com/html/4/element/h3.html)</h3>
<table (december.com/html/4/element/table.html) border=1>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<th (december.com/html/4/element/th.html) align=left></th>
<th (december.com/html/4/element/th.html) align=left></th>
<th (december.com/html/4/element/th.html) align=left></th>
<th (december.com/html/4/element/th.html) align=left></th>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
</table>
<h2> (december.com/html/4/element/h2.html)</h2>
<h3> (december.com/html/4/element/h3.html)</h3>
<table (december.com/html/4/element/table.html) border=1>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<th (december.com/html/4/element/th.html) align=left></th>
<th (december.com/html/4/element/th.html) align=left></th>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
</table>
<br> (december.com/html/4/element/br.html)
<h3> (december.com/html/4/element/h3.html)</h3>
<table (december.com/html/4/element/table.html) border=1>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<th (december.com/html/4/element/th.html) align=left></th>
<th (december.com/html/4/element/th.html) align=left></th>
<th (december.com/html/4/element/th.html) align=left></th>
</tr>
<tr> (december.com/html/4/element/tr.html)
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
</table>
<br> (december.com/html/4/element/br.html)

<br> (december.com/html/4/element/br.html)
<h3> (december.com/html/4/element/h3.html)</h3>
<table (december.com/html/4/element/table.html) border=1>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<th (december.com/html/4/element/th.html) align=left></th>
</tr>
<tr> (december.com/html/4/element/tr.html)
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
</table>
<br> (december.com/html/4/element/br.html)
<h3> (december.com/html/4/element/h3.html)</h3>
<table (december.com/html/4/element/table.html) border=1>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<th (december.com/html/4/element/th.html) align=left></th>
<th (december.com/html/4/element/th.html) align=left></th>
<th (december.com/html/4/element/th.html) align=left></th>
<th (december.com/html/4/element/th.html) align=left></th>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
</table>
<h3> (december.com/html/4/element/h3.html)</h3>
<table (december.com/html/4/element/table.html) border=1>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<th (december.com/html/4/element/th.html) align=left></th>
<th (december.com/html/4/element/th.html) align=left></th>
<th (december.com/html/4/element/th.html) align=left></th>
<th (december.com/html/4/element/th.html) align=left></th>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
<tr> (december.com/html/4/element/tr.html)
<th (december.com/html/4/element/th.html) align=left></th>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
<td (december.com/html/4/element/td.html) align=left></td>
</tr>
</table>
<hr> (december.com/html/4/element/hr.html)
</body>

sbrv · Guest Карма: 388 поощрить/наказать

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

если не сложно вышли на sbrv@yandex.ru

dkrnl · Guest Карма: 388 поощрить/наказать

zaartix можно на dkrnl@yandex.ru, а лучше на фтп какойнить.
спасибо.

phprus

zaartix
Отправь мне пожалуйста этот архив на email phprus@gmail.com

Maus

zaartix
Почему бы Вам не выложить этот файл здесь, аттачем?

Sla_sh · Guest Карма: 388 поощрить/наказать

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

Stan

Артeм Дивинcкий wrote:

А что касается формулы:
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)

Скажите, пожалуйста, это правильно?

Guest · Карма: 388 поощрить/наказать

Выше упоминался скрипт выделения корней из русского слова:

Ant wrote:

phalanxx wrote:

Ну да. Надо выделить корень, только не во всех словах, а исключить всякие предлоги и союзы из текста.

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

Вот ссылка:
Эвристическое (без словаря) извлечение корня из русского слова. (forum.dklab.ru/php/advises/HeuristicWithoutTheDictionaryExtractionOfARootFromRussianWord.html)

Eric-S

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

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

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

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

Code (any language):

скопировать код в буфер обмена

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

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

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

Blagotvor

алгоритмы алгоритмами... но может быть все же есть у кого ни будь готовая функция сравнения на PHP? мне необходимо сделать проверку входящего текста с уже имеющимся в базе, чтобы исключать повторы или сильные совпадения.

Guest · Карма: 388 поощрить/наказать

<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[implode('',$permutation)]))
                for ($j = rand(77,111); $j > 0; $j--)
                    array_swap($permutation);
            $registrator[implode('', $this->permuts[$i] = $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('|[a-zа-я\-\d]{3,99}|i', $sen, $m);
    return $m[0];
}
?>

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

leosun

Ну и итоговый ответ я думаю, вот

[php]
<?
$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'][md5(rtrim($big[$i].' '.$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'][md5(rtrim($small[$i].' '.$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>
[/php]

Evgensss · Guest Карма: 388 поощрить/наказать

zaartix wrote:

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

Кто может, вышлите пожалуйста этот архив на Evgen@ksu.ks.ua

Tsvetkov · Guest Карма: 388 поощрить/наказать

Blagotvor wrote:

алгоритмы алгоритмами... но может быть все же есть у кого ни будь готовая функция сравнения на PHP? мне необходимо сделать проверку входящего текста с уже имеющимся в базе, чтобы исключать повторы или сильные совпадения.

Вот, есть такое интересное решение: zendframework.ru/articles/zend-filter-keywords
Может кому будет полезно :)

Hunter Igor · Guest Карма: 388 поощрить/наказать

Blagotvor wrote:

алгоритмы алгоритмами... но может быть все же есть у кого ни будь готовая функция сравнения на PHP? мне необходимо сделать проверку входящего текста с уже имеющимся в базе, чтобы исключать повторы или сильные совпадения.

Code (php):

скопировать код в буфер обмена

Не оптимизировал - некогда, но оно работает.

dimagolov

Hunter Igor, eregi_* is depreciated in php 5.3.x

	Разное :: PHP :: Форум dkLab и Denwer Forum Index	All times are GMT + 3 Hours
Page 1 of 1		Email to a Friend.