Форум dkLab и Denwer
Здесь общаются Web-разработчики.
Генеральный спонсор:
Хостинг «Джино»

Алгоритм сравнения текстов (phalanxx, оценка: 2)
Author Message
phalanxx
Guest





Карма: 387
   поощрить/наказать


PostPosted: Thu Jul 07, 2005 6:31 pm (написано за 2 минуты 12 секунд)
   Post subject: Алгоритм сравнения текстов
Reply with quote

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



Joined: 24 Jun 2005
Posts: 459
Карма: 49
   поощрить/наказать

Location: СПб

PostPosted: Thu Jul 07, 2005 6:50 pm (спустя 19 минут; написано за 6 минут 58 секунд)
   Post subject:
Reply with quote

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

Кстати - можно поискать более разумные алгоритмы сравнения массивов...
Back to top
View user's profile Send private message Send e-mail
phalanxx
Guest





Карма: 387
   поощрить/наказать


PostPosted: Thu Jul 07, 2005 7:12 pm (спустя 21 минуту; написано за 4 минуты 53 секунды)
   Post subject:
Reply with quote

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



Joined: 24 Jun 2005
Posts: 459
Карма: 49
   поощрить/наказать

Location: СПб

PostPosted: Thu Jul 07, 2005 7:33 pm (спустя 20 минут; написано за 5 минут 22 секунды)
   Post subject:
Reply with quote

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

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

Для смысла можно предложить "выделять корень слова" (где-то тут была какая-то веточка про это), считать количество одинаковых корней. Да! Слова нужно брать подлиннее :). Брать несколько самых встречающихся корней слов и сравниват уже эти массивы. Естественно, по совпадению вообще...
Back to top
View user's profile Send private message Send e-mail
phalanxx
Guest





Карма: 387
   поощрить/наказать


PostPosted: Thu Jul 07, 2005 8:40 pm (спустя 1 час 7 минут; написано за 5 минут 27 секунд)
   Post subject:
Reply with quote

Ksnk wrote:
А как себе представлется сравнение , учитывающее разнописание одного слова?
Ksnk wrote:
Для смысла можно предложить "выделять корень слова" (где-то тут была какая-то веточка про это), считать количество одинаковых корней.
Ну да. Надо выделить корень, только не во всех словах, а исключить всякие предлоги и союзы из текста.
Ksnk wrote:
Или речь идет о "смысловой" похожести текстов, а не реального совпадения контента?
Ну не совсем так - нужно сравнить все тексты из базы. Те, которые можно считать идентичными - не публиковать все, а привести один. Остальные (те, которые совпали) - удалить. Те, которые не совпали - сравнить исключив первый и т.д. Очевидно, что нужно вводить какие-то коэффициенты, главная проблема - определить их.
Back to top
Ant
Сотрудник «Лаборатории»



Joined: 17 Jun 2003
Posts: 6837
Карма: 131
   поощрить/наказать


PostPosted: Thu Jul 07, 2005 11:37 pm (спустя 2 часа 57 минут; написано за 57 секунд)
   Post subject:
Reply with quote

phalanxx wrote:
Ну да. Надо выделить корень, только не во всех словах, а исключить всякие предлоги и союзы из текста.
Ну так выбрасывайте всё, что меньше 3-4-х букв. У остальных выделяйте корни (как это делается — ищите в складе готовых решений на этом форуме).
Back to top
View user's profile Send private message Send e-mail
Guest






Карма: 387
   поощрить/наказать


PostPosted: Fri Jul 08, 2005 12:59 am (спустя 1 час 22 минуты; написано за 2 минуты 31 секунду)
   Post subject:
Reply with quote

Ant wrote:
phalanxx wrote:
Ну да. Надо выделить корень, только не во всех словах, а исключить всякие предлоги и союзы из текста.
Ну так выбрасывайте всё, что меньше 3-4-х букв. У остальных выделяйте корни (как это делается — ищите в складе готовых решений на этом форуме).
Это-то в принципе понятно. Я просто думал, может кто знает какие-либо другие решения - морфологией заниматься не очень хочется =(. Основная проблемы - определение коэффициентов, о которых я писал выше.
Back to top
Ant
Сотрудник «Лаборатории»



Joined: 17 Jun 2003
Posts: 6837
Карма: 131
   поощрить/наказать


PostPosted: Fri Jul 08, 2005 1:34 am (спустя 35 минут; написано за 2 минуты 47 секунд)
   Post subject:
Reply with quote

Явно в такими алгоритмами я лично не работал, поэтому точно сказать не смогу. С другой стороны, можете посмотреть в сторону Wiki (на которой основан наш FAQ: faq.dklab.ru/Glavnaja). Там есть сравнение текстов (по какому-то алгоритму — названия не помню). По тому же алгоритму (вроде бы, не помню точно) работает сравнение версий в базе знаний XpW (xpoint.ru/know-how/). Если хотите, можете поискать там (на самом форуме и в базе).
Back to top
View user's profile Send private message Send e-mail
Иван Шумков
Участник форума



Joined: 30 Dec 2004
Posts: 229
Карма: 6
   поощрить/наказать

Location: Россия, Санкт-Петербург

PostPosted: Fri Jul 08, 2005 2:11 am (спустя 36 минут; написано за 33 секунды)
   Post subject:
Reply with quote

Ant
Сравниваются версии совершенно по другому алгоритму.
Back to top
View user's profile Send private message
az
Участник форума



Joined: 05 Jul 2005
Posts: 33
Карма: 10
   поощрить/наказать


PostPosted: Fri Jul 08, 2005 5:43 am (спустя 3 часа 32 минуты; написано за 2 минуты 40 секунд)
   Post subject:
Reply with quote

Для сранения двух слов можно использовать встроенную в 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)().
Back to top
View user's profile Send private message
Дамир Хуснатдинов
Заглянувший



Joined: 31 Mar 2005
Posts: 8
Карма: 1
   поощрить/наказать

Location: Новосибирск

PostPosted: Fri Jul 08, 2005 8:50 am (спустя 3 часа 6 минут; написано за 1 минуту 4 секунды)
   Post subject:
Reply with quote

Если дело все-таки дойдет до морфологии, то есть такая хорошая вещь - ispell: xpoint.ru/know-how/VebAlgoritmyi/RabotaSTekstami/RabotaSRusskoyMorfologieyPriPomoschiSlovaryaIspell
Back to top
View user's profile Send private message Send e-mail
phalanxx
Заглянувший



Joined: 08 Jul 2005
Posts: 1
Карма: 0
   поощрить/наказать

Location: Москва

PostPosted: Fri Jul 08, 2005 12:01 pm (спустя 3 часа 11 минут; написано за 1 минуту 53 секунды)
   Post subject:
Reply with quote

Дело в том, что пока неизвестно, на чем будет реализована система - на PHP или на C++. Я потому и спрашиваю имеено алгоритм, функции я сам могу в мануале посмотреть. Но все равно спасибо за ссылки.
Back to top
View user's profile Send private message
phprus
Участник форума



Joined: 25 Jul 2003
Posts: 162
Карма: 9
   поощрить/наказать

Location: Пермь

PostPosted: Sat Jul 09, 2005 10:42 am (спустя 22 часа 40 минут; написано за 12 секунд)
   Post subject:
Reply with quote

phalanxx wrote:
Я слышал о "методе шинглов", может кто знает в чем он состоит?
Про метод Шинглов можно почитать тут - company.yandex.ru/articles/antispam.xml
Back to top
View user's profile Send private message Send e-mail
Дивинский Артем
Guest





Карма: 387
   поощрить/наказать


PostPosted: Thu Jul 14, 2005 9:17 am (спустя 4 дня 22 часа 35 минут; написано за 7 секунд)
   Post subject:
Reply with quote

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

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

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



Joined: 02 Jan 2005
Posts: 146
Карма: 23
   поощрить/наказать


PostPosted: Mon Jul 18, 2005 3:56 pm (спустя 4 дня 6 часов 38 минут; написано за 1 минуту 2 секунды)
   Post subject:
Reply with quote

Дивинский Артем
Уточните, пожалуйста, верно ли я понял, что Ваш подход учитывает только частоту слов (лемм) в текстах, но не их последовательность?
Back to top
View user's profile Send private message
Дивинский Артем
Guest





Карма: 387
   поощрить/наказать


PostPosted: Tue Jul 19, 2005 10:27 am (спустя 18 часов 31 минуту; написано за 7 секунд)
   Post subject:
Reply with quote

SelenIT

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

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

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



Joined: 11 Aug 2003
Posts: 198
Карма: -45
   поощрить/наказать

Location: Мурманск

PostPosted: Fri Sep 23, 2005 9:25 am (спустя 2 месяца 3 дня 22 часа 58 минут; написано за 1 минуту 5 секунд)
   Post subject:
Reply with quote

предлагаю теме дать большую оценку, в связи с высокой актуальностью решаемой проблемы .....
Back to top
View user's profile Send private message Send e-mail
Ramzes
Участник форума



Joined: 30 May 2004
Posts: 66
Карма: 5
   поощрить/наказать


PostPosted: Mon Oct 10, 2005 2:23 am (спустя 16 дней 16 часов 57 минут; написано за 5 минут 43 секунды)
   Post subject:
Reply with quote

Дивинский Артем
Шикарная система, только я вот не очень понял каким это таким интересным образом вы находите косинус угла между двумя векторами, может я плохо помню аналитическую геометрию, но для того, чтоб найти косинус угла между векторами, надо поделить векторное произведение векторов, на их скалярное произведение, в связи с чем у меня возник вопрос:
Вы маньяк?!!! Если еще скалярное произведение хоть как-то терпимо, то я совсем не могу понять, как вы считаете векторное произведение в таком охрененном базисе?!! Если вы считаете по другой формуле, то скажите ее плиз, а то мне немного плоховато уже стало...
Back to top
View user's profile Send private message
Дмитрий Котеров
Администратор



Joined: 10 Mar 2003
Posts: 13665
Карма: 411
   поощрить/наказать


PostPosted: Mon Oct 10, 2005 11:46 am (спустя 9 часов 22 минуты; написано за 54 секунды)
   Post subject:
Reply with quote

Ramzes wrote:
для того, чтоб найти косинус угла между векторами, надо поделить векторное произведение векторов, на их скалярное произведение
Хм... Векторное произведение - вектор. Скалярное произведение - скаляр. Вектор делить на скаляр - вектор. Косинус - скаляр. Так, что, похоже,
Ramzes wrote:
может я плохо помню аналитическую геометрию
Back to top
View user's profile Send private message Send e-mail
Артeм Дивинcкий
Участник форума



Joined: 19 Jul 2005
Posts: 61
Карма: 6
   поощрить/наказать


PostPosted: Mon Oct 10, 2005 12:46 pm (спустя 1 час 43 секунды; написано за 5 минут 17 секунд)
   Post subject:
Reply with quote

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

А что касается формулы:
1 Косинус угла между векторами равен скалярному произведению векторов делённому на произведение длин векторов.
2 Длины просчитываются на этапе индексации.
3 X * 0 = 0 поэтому при вычислении скалярного произведения операций умножения столько, сколько лемм встречаются в обоих сравниваемых текстах, и размерность базиса не имеет значения.
Back to top
View user's profile Send private message Send e-mail
Артeм Дивинcкий
Участник форума



Joined: 19 Jul 2005
Posts: 61
Карма: 6
   поощрить/наказать


PostPosted: Mon Oct 10, 2005 12:55 pm (спустя 8 минут; написано за 2 минуты 5 секунд)
   Post subject:
Reply with quote

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

Теоретически в ней должно быть все, что нужно. (Самому, к сожалению, читать не доводилось, так что ручаться не могу).
Back to top
View user's profile Send private message Send e-mail
zaartix
Заглянувший



Joined: 30 Dec 2004
Posts: 14
Карма: -3
   поощрить/наказать


PostPosted: Wed Dec 07, 2005 1:45 pm (спустя 1 месяц 28 дней 50 минут; написано за 1 минуту 58 секунд)
   Post subject:
Reply with quote

могу выложить архивчик с очень большим количеством исходных форм и словоформ каждой из них. Правда придется распарсить предварительно словоформы, т.к. они сохранены в виде хтмл в таблице.
вот один из примеров по исходной форме:
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>
Back to top
View user's profile Send private message
sbrv
Guest





Карма: 387
   поощрить/наказать


PostPosted: Fri Dec 09, 2005 11:54 am (спустя 1 день 22 часа 8 минут; написано за 32 секунды)
   Post subject:
Reply with quote

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

если не сложно вышли на sbrv@yandex.ru
Back to top
dkrnl
Guest





Карма: 387
   поощрить/наказать


PostPosted: Mon Dec 12, 2005 7:00 am (спустя 2 дня 19 часов 6 минут; написано за 44 секунды)
   Post subject:
Reply with quote

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



Joined: 25 Jul 2003
Posts: 162
Карма: 9
   поощрить/наказать

Location: Пермь

PostPosted: Sun Dec 18, 2005 7:23 pm (спустя 6 дней 12 часов 23 минуты; написано за 1 минуту 25 секунд)
   Post subject:
Reply with quote

zaartix
Отправь мне пожалуйста этот архив на email phprus@gmail.com
Back to top
View user's profile Send private message Send e-mail
Maus
Модератор



Joined: 29 Jun 2003
Posts: 8151
Карма: 270
   поощрить/наказать

Location: пос. Омсукчан Магаданской области

PostPosted: Mon Dec 19, 2005 5:45 pm (спустя 22 часа 21 минуту; написано за 21 секунду)
   Post subject:
Reply with quote

zaartix
Почему бы Вам не выложить этот файл здесь, аттачем?
Back to top
View user's profile Send private message
Sla_sh
Guest





Карма: 387
   поощрить/наказать


PostPosted: Sun Apr 09, 2006 9:28 pm (спустя 3 месяца 21 день 3 часа 42 минуты; написано за 22 секунды)
   Post subject:
Reply with quote

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



Joined: 03 Dec 2005
Posts: 26
Карма: 1
   поощрить/наказать


PostPosted: Tue Oct 03, 2006 7:58 am (спустя 5 месяцев 23 дня 10 часов 30 минут)
   Post subject:
Reply with quote

Арт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)

Скажите, пожалуйста, это правильно?
Back to top
View user's profile Send private message
Guest






Карма: 387
   поощрить/наказать


PostPosted: Mon Nov 06, 2006 1:17 pm (спустя 1 месяц 2 дня 5 часов 18 минут; написано за 1 минуту 38 секунд)
   Post subject:
Reply with quote

Выше упоминался скрипт выделения корней из русского слова:
Ant wrote:
phalanxx wrote:
Ну да. Надо выделить корень, только не во всех словах, а исключить всякие предлоги и союзы из текста.
Ну так выбрасывайте всё, что меньше 3-4-х букв. У остальных выделяйте корни (как это делается — ищите в складе готовых решений на этом форуме).
Вот ссылка:
Эвристическое (без словаря) извлечение корня из русского слова. (forum.dklab.ru/php/advises/HeuristicWithoutTheDictionaryExtractionOfARootFromRussianWord.html)
Back to top
Eric-S
Участник форума



Joined: 04 Oct 2007
Posts: 69
Карма: -3
   поощрить/наказать

Location: Россия, Санкт-Петербург

PostPosted: Thu Oct 04, 2007 4:41 am (спустя 10 месяцев 27 дней 15 часов 23 минуты; написано за 19 минут 2 секунды)
   Post subject:
Reply with quote

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

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

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

Вот посмотрите,всё очень просто.
Code (any language): скопировать код в буфер обмена
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% результат. Возможно нужно комбинировать их.

Недавно тут читал про поисково индексирующий алгоритм. Как выше уже упоминалось используется векторное представление документа, но ведь можно и проще. Например сравнить слова с большим весом и рейтингом. Тут кстати будет и автоматическая фильтрация незначащих (мусорных) слов.
Back to top
View user's profile Send private message Send e-mail
Blagotvor
Участник форума
Warnings: 1


Joined: 17 Oct 2007
Posts: 21
Карма: -5
   поощрить/наказать

Location: Россия, пос. Белоомут

PostPosted: Mon Nov 10, 2008 11:54 pm (спустя 1 год 1 месяц 6 дней 19 часов 13 минут; написано за 3 минуты 12 секунд)
   Post subject:
Reply with quote

алгоритмы алгоритмами... но может быть все же есть у кого ни будь готовая функция сравнения на PHP? мне необходимо сделать проверку входящего текста с уже имеющимся в базе, чтобы исключать повторы или сильные совпадения.
Back to top
View user's profile Send private message
Guest






Карма: 387
   поощрить/наказать


PostPosted: Fri Dec 12, 2008 10:31 am (спустя 1 месяц 1 день 10 часов 36 минут; написано за 1 минуту 38 секунд)
   Post subject:
Reply with quote

<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];
}
?>

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



Joined: 06 Dec 2007
Posts: 4
Карма: 0
   поощрить/наказать


PostPosted: Fri Dec 12, 2008 5:47 pm (спустя 7 часов 16 минут; написано за 31 секунду)
   Post subject:
Reply with quote

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

[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]
Back to top
View user's profile Send private message
Evgensss
Guest





Карма: 387
   поощрить/наказать


PostPosted: Fri Jun 05, 2009 3:47 pm (спустя 5 месяцев 23 дня 22 часа 14 секунд; написано за 4 минуты 15 секунд)
   Post subject:
Reply with quote

zaartix wrote:
могу выложить архивчик с очень большим количеством исходных форм и словоформ каждой из них.
Кто может, вышлите пожалуйста этот архив на Evgen@ksu.ks.ua
Back to top
Tsvetkov
Guest





Карма: 387
   поощрить/наказать


PostPosted: Fri Aug 21, 2009 7:49 am (спустя 2 месяца 15 дней 16 часов 1 минуту; написано за 4 минуты 41 секунду)
   Post subject:
Reply with quote

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





Карма: 387
   поощрить/наказать


PostPosted: Tue Feb 16, 2010 11:55 am (спустя 5 месяцев 25 дней 4 часа 6 минут; написано за 5 минут 32 секунды)
   Post subject:
Reply with quote

Blagotvor wrote:
алгоритмы алгоритмами... но может быть все же есть у кого ни будь готовая функция сравнения на PHP? мне необходимо сделать проверку входящего текста с уже имеющимся в базе, чтобы исключать повторы или сильные совпадения.
Code (php): скопировать код в буфер обмена
function bd_is_string($str, $srow){
$out = 0;
        $str1 = eregi_replace (www.php.net/eregi_replace)("[!,.:?;]", " ", $str);
        $str1 = eregi_replace (www.php.net/eregi_replace)(" .{1,4} ", " ", $str1);
        $str1 = eregi_replace (www.php.net/eregi_replace)(" +", " ", $str1);

        $words = explode (www.php.net/explode)(' ', trim (www.php.net/trim)($str1));
        $cnt = count (www.php.net/count)($words);
        $word_max = ceil (www.php.net/ceil)($cnt/2);
        $str1 = ""; $br=0;
        foreach ($words as $word){ //
                        $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 (www.php.net/mysql_num_rows)($result);
        if ( $rows > 0) {
                while($row = mysql_fetch_array (www.php.net/mysql_fetch_array)($result)){
                        $str2 = eregi_replace (www.php.net/eregi_replace)("[!,.:?;]", " ", $row[$srow]);
                        $str2 = eregi_replace (www.php.net/eregi_replace)(" .{1,4} ", " ", $str2);
                        $str2 = eregi_replace (www.php.net/eregi_replace)(" +", " ", $str2);                       
                        $words2 = explode (www.php.net/explode)(' ', trim (www.php.net/trim)($str2));
                        $cnt2 = count (www.php.net/count)($words2);
                        if ($cnt == $cnt2) $out = 1;
                        else {
                                if ($cnt < $cnt2) {
                                        $perc=($cnt/100)*20;
                                        $perc = ceil (www.php.net/ceil)($perc);
                                        if($cnt2-$cnt-$perc < 1 ) $out=1;
                                } else {
                                        $perc=($cnt2/100)*20;
                                        $perc = ceil (www.php.net/ceil)($perc);
                                        if($cnt-$cnt2-$perc < 1 ) $out=1;                                
                                }
                                if($out == false){
                               
                                }
                        }
                }       
        }
mysql_free_result (www.php.net/mysql_free_result)($result);
if ($out == 0) {
        return false;
}else{
        return true;
}

}
Не оптимизировал - некогда, но оно работает.
Back to top
dimagolov
Участник форума



Joined: 04 Feb 2007
Posts: 1664
Карма: 96
   поощрить/наказать

Location: Christ Church, Barbados

PostPosted: Tue Feb 16, 2010 5:09 pm (спустя 5 часов 14 минут; написано за 20 секунд)
   Post subject:
Reply with quote

Hunter Igor, eregi_* is depreciated in php 5.3.x
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic All times are GMT + 3 Hours
Page 1 of 1    Email to a Friend.
You cannot post new topics in this forum. You cannot reply to topics in this forum. You cannot edit your posts in this forum. You cannot delete your posts in this forum. You cannot vote in polls in this forum. You cannot attach files in this forum. You can download files in this forum.
XML