Алгоритм поиска статей с похожим текстом

Question

У меня есть много статей в базе данных (с заголовком, текстом), я ищу алгоритм, чтобы найти X наиболее похожих статей, что-то вроде Stack Overflow "Связанные вопросы", когда вы задаете вопрос.

Я попробовал поискать в Google, но нашел только страницы о других "похожих текстовых" проблемах, что-то вроде сравнения каждой статьи со всеми остальными и сохранения где-то сходства. ТАК делает это в "реальном времени" над текстом, который я только что напечатал.

Как?

Answer 1

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

Что-то вроде Lucene - это путь. Вы индексируете все свои документы, а затем, когда хотите найти документы, похожие на данный документ, вы превращаете данный документ в запрос и выполняете поиск по индексу. Внутренне Lucene будет использовать tf-idf и инвертированный индекс, чтобы весь процесс занимал количество времени, пропорциональное количеству документов, которые могут совпадать, а не общее количество документов в коллекции.

Answer 2

Это зависит от вашего определения подобного.

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

1) "Это отличная книга"

2) "Это не великие книги"

(Количество букв, которые нужно удалить, вставить, удалить или изменить, чтобы превратить (2) в (1), называется "расстояние редактирования".)

Для реализации этого вы хотели бы посетить каждый обзор программно. Возможно, это не так дорого, как кажется, и если это слишком дорого, вы можете выполнить сравнения в качестве фоновой задачи и сохранить n-Most-similiar в самом поле базы данных.

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

3) "Французская революция была бла-бла, война и мир, бла-бла, Франция". -> Франция / Французская (2) Революция (1) Война (1) Мир (1) (обратите внимание, что словарь использовался для объединения Франции и французского)

4) "Эта книга - бла-бла, революция во французской кухне". -> Франция (1) Революция (1)

Чтобы реализовать это, вы бы хотели определить "ключевые слова" в обзоре, когда он был создан / обновлен, и найти похожие обзоры, используя эти ключевые слова в предложении where запроса (в идеале - полнотекстовый поиск, если база данных поддерживает его).), возможно, с последующей обработкой набора результатов для оценки найденных кандидатов.

Книги также имеют категории - триллерные сюжеты во Франции похожи на исторические исследования Франции и так далее? Метаданные помимо заголовка и текста могут быть полезны для сохранения релевантности результатов.

Answer 3

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

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

Answer 4

Вы можете использовать 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

Answer 5

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

Answer 6

Я предлагаю проиндексировать ваши статьи с помощью Apache Lucene, высокопроизводительной, полнофункциональной библиотеки текстового поискового движка, полностью написанной на Java. Это технология, подходящая практически для любого приложения, требующего полнотекстового поиска, особенно кросс-платформенного. После индексации вы можете легко найти соответствующие статьи.

Answer 7

Отдельное предложение Lucene для полного текста, но обратите внимание, что Java не является обязательным требованием; Порт.NET доступен. Также см. Главную страницу Lucene для ссылок на другие проекты, включая Lucy, порт C.

Answer 8

ТАК делает сравнение только по заголовку, а не по основному тексту вопроса, а только по довольно коротким строкам.

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

Answer 9

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

К сожалению, я не знаю ни одного инструмента, который бы позволял вам это делать (хотя мне было бы интересно найти один)

Answer 10

Я попробовал какой-то метод, но ни один из них не работает хорошо. Один из них может получить относительно достоверный результат, например, такой: во-первых: получить код Google SimHash для каждого абзаца всего текста и сохранить его в базе данных. Второе: индекс для кода SimHash. Третье: обработайте ваш текст для сравнения, как описано выше, получите код SimHash и выполните поиск по всему тексту по индексу SimHash, который, кроме того, образует расстояние Хэмминга, например 5-10. Затем сравните сходство с термином вектор. Это может работать для больших данных.

Answer 11

Ссылка в ответе @alex77 указывает на коэффициент Соренсена-Дайса, который был независимо обнаружен автором этой статьи - статья очень хорошо написана и заслуживает прочтения.

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

• трехбуквенные пары слов, которые содержат одну орфографическую ошибку, например [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>

Обратите внимание на преднамеренное написание в последнем примере: абрака дабра против абрача бадра. Несмотря на то, что дополнительная коррекция биграммы не применяется, указанный коэффициент равен 0,9. С коррекцией это было бы 0,91.

Надеюсь, это поможет другим, кто наткнется на эту ветку.

Answer 12

На основе примера текста эта программа перечисляет тексты репозитория, отсортированные по сходству: простая реализация пакета слов в 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);
}

Answer 13

Если вы ищете слова, которые намотаны одинаково, вы можете преобразовать в soundex и слова soundex, чтобы соответствовать... работал для меня

Answer 14

Вы можете использовать полнотекстовый индекс SQL Server, чтобы получить разумное сравнение. Я полагаю, что SO использует вызов ajax, который выполняет запрос, чтобы вернуть похожие вопросы.

Какие технологии вы используете?

Answer 15

Вероятно, самый простой и быстрый способ сравнить сходство между рефератами - использовать концепцию множества. Сначала преобразуйте абстрактные тексты в набор слов. Затем проверьте, насколько каждый набор перекрывается. Функция набора Python очень хорошо подходит для выполнения этой задачи. Вы будете удивлены, увидев, насколько хорошо этот метод сравнивается с теми вариантами "похожих / связанных документов", которые предоставляются GScholar, ADS, WOS или Scopus.