Алгоритм поиска статей с похожим текстом
https://stackoverflow.com/questions/246961
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
У меня есть много статей в базе данных (с заголовком и текстом), я ищу алгоритм для поиска X наиболее похожих статей, что-то вроде «Похожие вопросы» Stack Overflow, когда вы задаете вопрос.
Я попробовал поискать в Google, но нашел только страницы, посвященные другим проблемам с «похожим текстом», например, сравнение каждой статьи со всеми остальными и сохранение где-то сходства.ТАК делает это в «реальном времени» с текстом, который я только что набрал.
Как?
Решение
Изменить расстояние не является вероятным кандидатом, так как он будет зависеть от правописания/порядка слов и гораздо более затратен в вычислительном отношении, чем заставляет вас думать Уилл, учитывая размер и количество документов, которые вы действительно заинтересованы в поиске.
Что-то вроде Lucene — лучший вариант.Вы индексируете все свои документы, а затем, когда хотите найти документы, похожие на данный документ, вы превращаете данный документ в запрос и выполняете поиск по индексу.Внутри компании Lucene будет использовать tf-idf и инвертированный индекс чтобы весь процесс занимал время, пропорциональное количеству документов, которые могут совпадать, а не общему количеству документов в коллекции.
Другие советы
Это зависит от вашего определения подобного.
А расстояние редактирования Алгоритм является стандартным алгоритмом для предложений словаря (латинского языка) и может работать с целыми текстами.Два текста похожи, если в них есть по сути одни и те же слова (буквы) в одном и том же порядке.Таким образом, следующие две рецензии на книги будут довольно похожими:
1) «Это замечательная книга»
2) «Это не великие книги»
(Количество букв, которые нужно удалить, вставить, удалить или изменить, чтобы превратить (2) в (1), называется «расстоянием редактирования».)
Чтобы реализовать это, вам нужно будет программно посещать каждый обзор.Возможно, это не так дорого, как кажется, и если это слишком дорого, вы можете выполнить сравнения в качестве фоновой задачи и сохранить n-наиболее похожих значений в самом поле базы данных.
Другой подход — понять структуру (латинских) языков.Если вы удалите короткие слова (без заглавных букв или в кавычках) и присвоите веса общим или уникальным словам (или префиксам), вы сможете провести байесовское сравнение.Две следующие рецензии на книги можно упростить и найти похожими:
3) «Французская революция была войной и миром Бла -Бла -Бла -Франс». -> Франция/Французская (2) Революция (1) Война (1) Мир (1) (Обратите внимание, что словарь использовался для объединения Франции и французского)
4) «Эта книга - бла -бла революция во французской кухне». -> Франция (1) Революция (1)
Чтобы реализовать это, вам нужно будет идентифицировать «ключевые слова» в обзоре, когда он был создан/обновлен, и для поиска похожих обзоров используйте эти ключевые слова в предложении «where» запроса (в идеале «полнотекстовый» поиск, если база данных его поддерживает). ), возможно, с последующей обработкой набора результатов для оценки найденных кандидатов.
У книг тоже есть категории: похожи ли триллеры, действие которых происходит во Франции, на исторические исследования Франции и так далее?Метаданные, помимо заголовка и текста, могут быть полезны для поддержания актуальности результатов.
Учебник по этому поводу связь похоже, это может быть то, что вам нужно.За ним легко следовать, и он работает очень хорошо.
Его алгоритм вознаграждает как общие подстроки, так и общий порядок этих подстрок, поэтому он должен довольно хорошо выбирать похожие заголовки.
Я предлагаю индексировать ваши статьи, используя Апач Лусене, высокопроизводительная полнофункциональная библиотека системы текстового поиска, полностью написанная на Java.Это технология, подходящая практически для любого приложения, требующего полнотекстового поиска, особенно кроссплатформенного..После индексации вы сможете легко найти соответствующие статьи.
Одним из распространенных алгоритмов является Самоорганизующаяся карта.Это тип нейронной сети, которая автоматически классифицирует ваши статьи.Затем вы можете просто найти на карте местоположение текущей статьи и все статьи рядом с ней связаны.Важная часть алгоритма заключается в том, как вы будете векторное квантование вашего ввода.Есть несколько способов работы с текстом.Вы можете хэшировать свой документ/заголовок, вы можете подсчитывать слова и использовать их как n-мерный вектор и т. д.Надеюсь, это поможет, хотя, возможно, я открыл для вас ящик Пандоры бесконечного путешествия в области искусственного интеллекта.
ТАК сравнение выполняется только по заголовку, а не по основному тексту вопроса, то есть только по довольно коротким строкам.
Вы можете использовать их алгоритм (не знаю, как он выглядит) в заголовке статьи и ключевых словах.Если у вас есть больше процессорного времени, в том числе и для тезисов ваших статей.
Поддерживаю предложение Lucene относительно полнотекстового варианта, но обратите внимание, что Java не является обязательным требованием; доступен порт .NET.Также см. главная страница Lucene для ссылок на другие проекты, в том числе Люси, порт 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 указывает на Коэффициент Соренсена-Дайса который был независимо обнаружен автором этой статьи - статья очень хорошо написана и ее стоит прочитать.
В итоге я использовал этот коэффициент для своих нужд.Однако исходный коэффициент может дать ошибочные результаты при работе с
- Пары слов из трех букв, содержащие одну орфографическую ошибку, например
[and,amd]и - Пары слов из трех букв, которые являются анаграммами, например.
[and,dan]
В первом случае Дайс ошибочно сообщает нулевой коэффициент, тогда как во втором случае коэффициент оказывается равным 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>Обратите внимание на преднамеренную опечатку в последнем примере:абракадабра против абракиБадра.Несмотря на то, что дополнительная коррекция биграмм не применяется, указанный коэффициент составляет 0,9.С учетом коррекции оно составило бы 0,91.
Надеюсь, это поможет другим, кто сталкивается с этой веткой.
Учитывая образец текста, эта программа выводит список текстов репозитория, отсортированных по сходству: простая реализация набора слов на C++.Алгоритм линеен по общей длине образца текста и текстов репозитория.Плюс программа многопоточная для параллельной обработки текстов репозитория.
Вот основной алгоритм:
class Statistics {
std::unordered_map<std::string, int64_t> _counts;
int64_t _totWords;
void process(std::string& token);
public:
explicit Statistics(const std::string& text);
double Dist(const Statistics& fellow) const;
bool IsEmpty() const { return _totWords == 0; }
};
namespace {
const std::string gPunctStr = ".,;:!?";
const std::unordered_set<char> gPunctSet(gPunctStr.begin(), gPunctStr.end());
}
Statistics::Statistics(const std::string& text) {
std::string lastToken;
for (size_t i = 0; i < text.size(); i++) {
int ch = static_cast<uint8_t>(text[i]);
if (!isspace(ch)) {
lastToken.push_back(tolower(ch));
continue;
}
process(lastToken);
}
process(lastToken);
}
void Statistics::process(std::string& token) {
do {
if (token.size() == 0) {
break;
}
if (gPunctSet.find(token.back()) != gPunctSet.end()) {
token.pop_back();
}
} while (false);
if (token.size() != 0) {
auto it = _counts.find(token);
if (it == _counts.end()) {
_counts.emplace(token, 1);
}
else {
it->second++;
}
_totWords++;
token.clear();
}
}
double Statistics::Dist(const Statistics& fellow) const {
double sum = 0;
for (const auto& wordInfo : _counts) {
const std::string wordText = wordInfo.first;
const double freq = double(wordInfo.second) / _totWords;
auto it = fellow._counts.find(wordText);
double fellowFreq;
if (it == fellow._counts.end()) {
fellowFreq = 0;
}
else {
fellowFreq = double(it->second) / fellow._totWords;
}
const double d = freq - fellowFreq;
sum += d * d;
}
return std::sqrt(sum);
}
Самый простой и быстрый способ сравнить сходство между рефератами, вероятно, — использовать концепцию множества.Сначала преобразуйте абстрактные тексты в набор слов.Затем проверьте, насколько каждый набор перекрывается.Функция set Python очень помогает при выполнении этой задачи.Вы будете удивлены, увидев, насколько хорошо этот метод сравнивается с вариантами «похожих/связанных статей», предоставляемыми GScholar, ADS, WOS или Scopus.
