Как проверить, содержится ли текст в другом?

Question

Я разрабатываю систему документов, которая каждый раз, когда создается новый, она должна обнаруживать и отбрасывать дубликаты в базе данных, содержащей около 500 000 записей.

В настоящее время я использую поисковую систему для извлечения 20 наиболее похожих документов и сравниваю их с новой, которую мы пытаемся создать. Проблема в том, что я должен проверить, похож ли новый документ (это легко с аналогичным_текстом), или даже если он содержится внутри другого текста, все эти операции, учитывая, что пользователь мог частично изменить текст (здесь проблема). Как я могу это сделать?

Например:

<?php 

$new = "the wild lion"; 

$candidates = array(
    'the dangerous lion lives in Africa',//$new is contained into this one, but has changed 'wild' to 'dangerous', it has to be detected as duplicate 
    'rhinoceros are native to Africa and three to southern Asia.' 
); 

foreach ($candidates as $candidate) { 
    if($candidate is similar or $new is contained in it) { 
     //Duplicated!! 
    } 
} 

Конечно, в моей системе документы больше чем 3 слов :)

Answer 1

Это временное решение, я использую:

function contained($text1, $text2, $factor = 0.9) { 
    //Split into words 
    $pattern= '/((^\p{P}+)|(\p{P}*\s+\p{P}*)|(\p{P}+$))/u'; 
    $words1 = preg_split($pattern, mb_strtolower($text1), -1, PREG_SPLIT_NO_EMPTY); 
    $words2 = preg_split($pattern, mb_strtolower($text2), -1, PREG_SPLIT_NO_EMPTY); 

    //Set long and short text 
    if (count($words1) > count($words2)) { 
     $long = $words1; 
     $short = $words2; 
    } else { 
     $long = $words2; 
     $short = $words1; 
    } 

    //Count the number of words of the short text that also are in the long 
    $count = 0; 
    foreach ($short as $word) { 
     if (in_array($word, $long)) { 
      $count++; 
     } 
    } 

    return ($count/count($short)) > $factor; 
} 

Answer 2

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

1. Индексирование документов, а затем поиск похожих документов. Таким образом, поисковые системы с открытым исходным кодом, такие как Solr, Sphinx или Zend Search Lucene, могут пригодиться.

2. Вы можете использовать sim hashing algorithm или shingling. Вкратце алгоритм simhash позволит вам вычислять аналогичные значения хэша для похожих документов. Таким образом, вы можете сохранить это значение по каждому документу и проверить, насколько похожи разные документы.

Другие алгоритмы, которые могут оказаться полезными, чтобы получить некоторые идеи являются:

1. Levenshtein distance

2. Bayesian filtering - SO Questions re Bayesian filtering. Первая ссылка в этом элементе списка указывает на байесовскую статью для фильтрации спама на Wiki, но этот алгоритм можно адаптировать к тому, что вы пытаетесь сделать.