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

Question

[Astrohas]

Нужно осуществить анализ схожести строки со строками из базы. Строки не длинные < 1024 символов. В какую сторону нужно копать?

Answer 1

[al_gon]

https://en.wikipedia.org/wiki/Category:String_simi...
chairnerd.seatgeek.com/fuzzywuzzy-fuzzy-string-mat...

С плагиатом сложнее. Сравние должно идти уже по структуре и смысловому набору.
Но грубое определение плагиата, где меняются слова и в предатотчном предложении его части, similarity measures тоже потянут.

Примитивное и наивное решение на питоне:

def dice_coefficient(a, b):
    a_bigrams = set(a)
    b_bigrams = set(b)
    overlap = len(a_bigrams & b_bigrams)
    return overlap * 2.0/(len(a_bigrams) + len(b_bigrams))

dice_coefficient("2","3")
=> 0.0
   dice_coefficient("2","23")
=> 0.6666666666666666
   dice_coefficient("Как осуществить анализ схожести строк и проверить на плагиат?","плагиат?")
=> 0.5454545454545454
   dice_coefficient("Как осуществить анализ схожести строк и проверить на плагиат?","плагиат dsfsf?")
=> 0.5405405405405406
   dice_coefficient("Как осуществить анализ схожести строк и проверить на плагиат?","плагиат dsfsf? fdedfdfdfgdgh")
=> 0.5
   dice_coefficient("Как осуществить анализ схожести строк и проверить на плагиат?","Как осуществить анализ схожести строк и проверить на плагиат?")
=> 1.0
   dice_coefficient("Как осуществить анализ схожести строк и проверить на плагиат?","Как осуществить?")
=> 0.8
   dice_coefficient("Как осуществить анализ схожести строк и проверить на плагиат","анализ схожести строк и проверить на плагиат?")
=> 0.9090909090909091

P.S.: Только в качестве примера и не рекомендации к использованию именно в таком виде.

Answer 2

[Максим Кудрявцев]

Нечеткий поиск. Алгоритм шинглов.

Answer 3

[Astrohas]

Решение следующее.
В подачу для начало даются тексты. Тексты канонизируются, разделяются на шинглы. Затем в таблицу базы данных (например Shingles) добавляются их контрольные суммы . Кроме этого добавляются форигном айди для текста, и позиция шингла. Когда нужно сравнить какойто текст на плагиат из базы, сравниваются контрольные суммы хешов. Сравнение текста на 20 000слов занимает около .5 секунды. Конечно же контрольные суммы и шинглы нового текста затем добавляются в базу.