Търсене на размити дубликати

Нека опишем на достъпен език принципа на алгоритмите за херпес, супер херпес и мегашингъл за сравняване на уеб документи.

Защо точно 84? Използването на 84 произволно избрани стойности на контролна сума ще улесни модифицирането на алгоритъма към алгоритъма на supershingles и megashingles, които са много по-малко ресурсоемки. Ще ги опиша след малко.

Препоръчвам да се въоръжите с химикал и лист хартия и образно да представите всяка от описаните по-долу стъпки под формата на рисунка.

И така, алгоритъмът на херпес зостер за уеб документи

Нека анализираме през какви етапи преминава текстът, подложен на сравнение:

  1. канонизация на текста;
  2. разцепване на херпес зостер;
  3. изчисляване на хешовете на херпес зостер с помощта на 84 статични функции;
  4. случаен избор на 84 стойности на контролна сума;
  5. сравнение, определяне на резултата.

1. Канонизиране на текста

Описах какво е канонизиране на текст в последната ми статия за алгоритъма за херпес зостер. Но ще повторя накратко. Канонизирането на текста привежда оригиналния текст в единна нормална форма.

Текстът е изчистен от предлози, съюзи, препинателни знаци, HTML тагове и други ненужни "боклуци", които не трябва да се включват в сравнението. В повечето случаи се предлага също да се премахнат прилагателните от текста, тъй като те не носят семантичен товар.

Също така, на етапа на канонизиране на текста, съществителните могат да бъдат намалени до именителен случай, единствено число или да бъдат оставени само корени от тях.

С канонизирането на текста можете да експериментирате и експериментирате, полето за действие тук е широко.

На изхода имаме текст, изчистен от "боклук" и готов за сравнение.

търсене

2.Разделяне на херпес зостер

Херпес зостер (eng) - скали, изолирани от члена на подпоследователност от думи.

Необходимо е да се изберат подпоследователности от думи от сравняваните текстове, които следват една след друга в 10 части (дължината на плочката). Изборът се припокрива, а не от край до край.

По този начин, като разделяме текста на подпоследователности, получаваме набор от шингли, равни на броя на думите минус дължината на шинглите плюс едно (брой_думи - дължина на шингли + 1).

Напомням ви, че действията за всеки от елементите се извършват за всеки от сравняваните текстове.

размити

3. Изчисляване на хешовете на херпес зостер с помощта на 84 статични функции

Това е най-интересният етап. Принципът на алгоритъма за шингли е да сравнява произволна извадка от контролни суми на шингли (подпоследователности) на два текста един с друг.

Проблемът с алгоритъма е броят на сравненията, защото това пряко влияе върху производителността. Увеличаването на броя на херпес зостер за сравнение се характеризира с експоненциален растеж на операциите, което ще повлияе критично на производителността.

Предлага се текстът да се представи като набор от контролни суми, изчислени с помощта на 84x уникални статични хеш функции.

Нека обясня: за всяка керемида се изчисляват 84 стойности на контролна сума с помощта на различни функции (например SHA1, MD5, CRC32 и т.н., общо 84 функции). Така че всеки от текстовете ще бъде представен, може да се каже, под формата на двумерен масив от 84 реда, където всеки ред характеризира съответната от 84-те функции за контролна сума.

От получените набори, 84 стойности ще бъдат избрани на случаен принцип за всеки от текстовете и сравнени помежду си в съответствие с функцията за контролна сума, чрез която е изчислен всеки от тях. Та за сравнениеще е необходимо да се извършат общо 84 операции.

търсене

4. Произволен избор на 84 стойности на контролна сума

Както описах по-горе, сравняването на елементите на всеки от 84-те масива един с друг изисква много ресурси. За да увеличим производителността, нека извършим случаен избор на контролни суми за всеки от 84-те реда на двуизмерен масив и за двата текста. Например, нека изберем най-малката стойност от всеки ред.

И така, на изхода имаме набор от минимални стойности на контролна сума на херпес зостер за всяка от хеш функциите.

текста

5. Сравнение, определяне на резултата

И последната стъпка е сравнението. Сравняваме 84 елемента от първия масив със съответните 84 елемента от втория масив, изчисляваме съотношението на същите стойности, от което получаваме резултата.

дубликати

Алгоритъм за херпес в PHP

Алгоритъмът shingles се използва за намиране на „подобни документи“ и определяне на степента на сходство между два текста. Например, имате сто текста (да кажем, че това са статии или новини) и трябва да намерите пренаписвания. Тези. текстове, които не са абсолютно еднакви помежду си, но до известна степен си приличат. Алгоритъмът за херпес зостер може да се използва за намиране на „препечатки“ на текстове или, например, за групиране на новини по история (здравейте на услугата Yandex.News). Въпреки факта, че в основната си версия алгоритъмът е доста прост, има много начини да го направите сложен и много различни вариации - supershingles, megashingles ... Ние ще внедрим основната версия на този алгоритъм без много проблеми в PHP.

Описание на алгоритъма

Така че имаме два текста. Трябва да определим дали си приличат. Какво правим?

  1. Почистваме текстовете от всякакви "боклуци". Това се нарича нормализация или канонизация.Долната линия е да премахнете всички препинателни знаци, предлози от текста, да преведете думите в малки букви.
  2. Разбиване на текста на шиндли. Това означава разделяне на текста на поредици от думи. Една шингла (последователност) ще съдържа 4 думи.
  3. Изчисляване на контролни суми на херпес зостер. Използване на функциите crc32, md5 или sha1.
  4. Разглеждаме колко херпес зонди (последователности от думи) присъстват в двата текста. За да направите това, просто трябва да намерите контролните суми, които са в първия текст и във втория.

Демо алгоритъм

Нека видим как работи алгоритъмът с малък пример. Да кажем, че имаме два текста.

За да имате стройна фигура, трябва да спортувате и да се храните правилно. Заповядайте в спортна зала "Искра" - бъдете здрави и красиви!

момичета Заповядайте в Спортен клуб Бътерфлай. Разполагаме с много тренажори и опитни инструктори, които ще ви кажат как да спортувате и да се храните правилно, за да имате стройна фигура и бодър дух.

На лицето пренапишете. Текстовете не са еднакви, но си приличат. Нека вземем първия текст и го изчистим, получаваме следното:

за да имате стройна фигура, трябва да спортувате, яжте правилно, елате във фитнеса, бъдете здрави здрави

момичета елате спортен клуб пеперуда имаме много симулатори опитни инструктори, които ще ви кажат да спортувате ядете правилно, за да имате стройна фигура бодър дух

Съставяме херпес зостер (последователности от думи). Нека една керемида ще се състои от 3 думи. Тогава за първия текст получаваме следните последователности: