У меня есть много статей в базе данных (с заголовком, текстом), я ищу алгоритм для поиска X самых похожих статей, например Qaru "Вопросы, относящиеся", когда вы задаете вопрос.
Я попробовал поиск по сайту, но нашел только страницы о других проблемах с аналогичным текстом, что-то вроде сравнения каждой статьи со всеми остальными и сохранения где-то сходства. SO делает это в "реальном времени" в тексте, который я только что напечатал.
Как?
Изменить расстояние не является вероятным кандидатом, так как это зависит от орфографии/словаря и намного более дорогостоящего, чем Уилл побуждая вас поверить, учитывая размер и количество документов, которые вам действительно интересны в поиске.
Что-то вроде Lucene - это путь. Вы индексируете все свои документы, а затем, когда вы хотите найти документы, похожие на данный документ, вы превращаете свой документ в запрос и выполняете поиск по индексу. Внутри Lucene будет использовать tf-idf и инвертированный индекс чтобы весь процесс занимал промежуток времени, пропорциональный количеству документов, которые могли бы соответствовать, а не общее количество документов в коллекции.
Это зависит от вашего определения аналогичного.
Алгоритм edit-distance является стандартным алгоритмом для предложений словаря латинского языка и может работать над целыми текстами. Два текста аналогичны, если они имеют в основном одни и те же слова (буквы eh) в том же порядке. Таким образом, следующие два обзора книг были бы довольно похожи:
1) "Это отличная книга"
2) "Это не великие книги"
(Число букв для удаления, вставки, удаления или изменения для поворота (2) в (1) называется "расстоянием редактирования".)
Чтобы реализовать это, вы захотите посетить каждый обзор программно. Это, возможно, не так дорого, как кажется, и если это слишком дорого, вы можете выполнять сравнения в качестве фоновой задачи и хранить n-наиболее похожие в самом поле базы данных.
Другой подход заключается в понимании структуры (латинских) языков. Если вы разделите короткие (не-capitialised или цитируемые) слова и присвойте весу словам (или префиксам), которые являются общими или уникальными, вы можете сравнить байесовские сравнения. Два следующих обзора книг могут быть подобранными и считаться похожими:
3) "Французская революция была бла-бла-бла-бла-бла-бла-бла, Франция". → Франция/Французский (2) Революция (1) Война (1) Мир (1) (обратите внимание, что словарь используется для объединения Франции и Франции)
4) "Эта книга - это бла-бла-а-а революция в французской кухне". → Франция (1) Революция (1)
Чтобы реализовать это, вы хотели бы идентифицировать ключевые слова в обзоре, когда он был создан/обновлен, а для поиска аналогичных отзывов используются эти ключевые слова в предложении where-запроса (в идеале "полный текст", если база данных поддерживает его), возможно, после обработки результатов, полученных для подсчета найденных кандидатов.
В книгах также есть категории - триллеры, установленные во Франции, похожие на исторические исследования Франции и т.д.? Метаданные, находящиеся за заголовком и текстом, могут быть полезны для сохранения соответствующих результатов.
Я предлагаю индексировать ваши статьи, используя Apache Lucene - высокопроизводительную полнофункциональную текстовую поисковую библиотеку, полностью написанную на Java. Это технология, подходящая практически для любого приложения, которое требует полнотекстового поиска, особенно межплатформенного. После индексирования вы можете легко найти связанные статьи.
Одним из распространенных алгоритмов является Self-Organizing Map. Это тип нейронной сети, который автоматически классифицирует ваши статьи. Затем вы можете просто найти местоположение, на котором находится текущая статья, и все статьи рядом с ним связаны. Важная часть алгоритма заключается в том, как вы вектор квантуете свои данные. Есть несколько способов сделать это с текстом. Вы можете хэшировать свой документ/заголовок, вы можете подсчитывать слова и использовать их как n-мерный вектор и т.д. Надеюсь, что это поможет, хотя я, возможно, открыл коробку Пандоры для вас бесконечного путешествия в ИИ.
SO делает сравнение только по заголовку, а не по основному тексту вопроса, поэтому только на довольно коротких строках.
Вы можете использовать свой алгоритм (не знаю, как это выглядит) в заголовке статьи и ключевых словах. Если у вас больше времени на сжигание, а также на тезисы ваших статей.
Второе предложение Lucene для полнотекстового текста, но обратите внимание, что Java не является обязательным требованием; доступен порт .NET. Также смотрите главную страницу Lucene для ссылок на другие проекты, включая Lucy, порт C.
Возможно, ваш поиск - это то, что делает перефразирование. У меня есть только поверхностное знание этого, но перефразирование - это концепция естественного языка, чтобы определить, действительно ли два фрагмента текста означают одно и то же - хотя могут использоваться совершенно разные слова.
К сожалению, я не знаю никаких инструментов, которые позволят вам сделать это (хотя мне было бы интересно найти его)
Вы можете использовать полнотекстовый индекс SQL Server для получения интеллектуального сравнения, я считаю, что SO использует вызов ajax, который выполняет запрос, чтобы возвращать похожие вопросы.
Какие технологии вы используете?
Если вы ищете слова, похожие на рану, вы можете преобразовать в soundex и слова soundex, чтобы они соответствовали... работали для меня
Я пробовал какой-то метод, но никто не работает хорошо. Один может получить относительно насыщенный результат: Во-первых: получите код Google SimHash для каждого абзаца всего текста и сохраните его в базе данных. Второй: индекс для кода SimHash. В-третьих: обработайте свой текст, сравниваемый, как указано выше, получите код SimHash и найдите весь текст по индексу SimHash, который отличается от расстояния Хэмминга как 5-10. Затем сравните симуляцию с вектором-вектором. Это может работать для больших данных.
вы можете использовать 1) Minhash/LSH https://en.wikipedia.org/wiki/MinHash
(также см.: http://infolab.stanford.edu/~ullman/mmds/book.pdf)
или
2) совместная фильтрация: https://en.wikipedia.org/wiki/Collaborative_filtering
Ссылка в @alex77 отвечает на Sorensen-Dice Coefficient, который был независимо открыт автором этой статьи - статья очень хорошо написана и стоит прочитать.
Я использовал этот коэффициент для своих нужд. Однако исходный коэффициент может давать ошибочные результаты при работе с
[and,amd] и[and,dan]В первом случае Dice ошибочно сообщает о нулевом коэффициенте, а во втором случае коэффициент становится равным 0,5, что является ошибочным.
Было предложено улучшение которое по существу состоит из взятия первого и последнего символов слова и создания дополнительного биграма.
На мой взгляд, улучшение действительно требуется только для трех буквенных слов - в более длинных словах другие биграмы имеют эффект буферизации, который покрывает проблему. Мой код, который реализует это улучшение, приведен ниже.
function wordPairCount(word)
{
var i,rslt = [],len = word.length - 1;
for(i=0;i < len;i++) rslt.push(word.substr(i,2));
if (2 == len) rslt.push(word[0] + word[len]);
return rslt;
}
function pairCount(arr)
{
var i,rslt = [];
arr = arr.toLowerCase().split(' ');
for(i=0;i < arr.length;i++) rslt = rslt.concat(wordPairCount(arr[i]));
return rslt;
}
function commonCount(a,b)
{
var t;
if (b.length > a.length) t = b, b = a, a = t;
t = a.filter(function (e){return b.indexOf(e) > -1;});
return t.length;
}
function myDice(a,b)
{
var bigrams = [],
aPairs = pairCount(a),
bPairs = pairCount(b);
debugger;
var isct = commonCount(aPairs,bPairs);
return 2*commonCount(aPairs,bPairs)/(aPairs.length + bPairs.length);
}
$('#rslt1').text(myDice('WEB Applications','PHP Web Application'));
$('#rslt2').text(myDice('And','Dan'));
$('#rslt3').text(myDice('and','aMd'));
$('#rslt4').text(myDice('abracadabra','abracabadra'));*{font-family:arial;}
table
{
width:80%;
margin:auto;
border:1px solid silver;
}
thead > tr > td
{
font-weight:bold;
text-align:center;
background-color:aqua;
}<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.0.0/jquery.min.js"></script>
<table>
<thead>
<tr>
<td>Phrase 1</td>
<td>Phrase 2</td>
<td>Dice</td>
</tr>
<thead>
<tbody>
<tr>
<td>WEB Applications</td>
<td>PHP Web Application</td>
<td id='rslt1'></td>
</tr>
<tr>
<td>And</td>
<td>Dan</td>
<td id='rslt2'></td>
</tr>
<tr>
<td>and</td>
<td>aMd</td>
<td id='rslt3'></td>
</tr>
<tr>
<td>abracadabra</td>
<td>abracabadra</td>
<td id='rslt4'></td>
</tr>
</tbody>
</table>Самый простой и быстрый способ сравнить сходство между тезисами - это, вероятно, использование концепции набора. Сначала преобразуйте абстрактные тексты в множество слов. Затем проверьте, насколько каждый набор перекрывается. Функция набора Python очень эффективна для выполнения этой задачи. Вы были бы удивлены, увидев, насколько хорошо этот метод сравнивается с теми "аналогичными/связанными документами", которые предоставляются GScholar, ADS, WOS или Scopus.