Алгоритъм за херпес зостер - блог
Два откъса захерпес зостер:
В допълнение, индексирането от търсачките на страници, генерирани от бази данни, генерира друг общ клас от външно малко различни документи: профили, форуми, продуктови страници в електронни магазини
Очевидно няма особени проблеми с пълните повторения, достатъчно е да съхраните контролната сума на текста в индекса и да игнорирате всички други текстове със същата контролна сума. Този метод обаче не работи за откриване дори на леко модифицирани документи.
Контролна сума (шинда) се изчислява за всеки десет думи от текста. Декалозите се припокриват, припокриват се, така че никой да не липсва. И тогава от целия набор от контролни суми (очевидно те са толкова, колкото има думи в документа минус 9), се избират само онези, които се делят, да речем, на 25. Тъй като стойностите на контролните суми са равномерно разпределени, критерият за вземане на проби по никакъв начин не е обвързан с характеристиките на текста. Ясно е, че повторението дори на един дескриптор е значителен признак за дублиране, но ако има много от тях, да речем, повече от половината, тогава с определена (лесно е да се оцени вероятността) увереност можем да кажем: копие е намерено! В края на краищата, една съвпадаща шингла в извадката съответства на приблизително 25 съвпадащи десет думи в пълния текст!
Очевидно по този начин можете да определите процента на припокриване на текста, да идентифицирате всичките му източници и т.н. Този изящен алгоритъм е въплътил старата мечта на доцентите: отсега нататък болезненият въпрос „от кого студентът е преписал тази курсова работа“ може да се счита за разрешен! Лесно е да се оцени делът на плагиатството във всяка статия.
За да не остане у читателя впечатлението, че извличането на информация е изключително западна наука, ще спомена един алтернативен алгоритъм за определяне на почти дубликати, изобретен ивъплътен в нашия Yandex [ilyinsky]. Той се възползва от факта, че повечето търсачки вече имат обърнат файлов индекс (или обърнат индекс) и този факт е полезен за намиране на почти дубликати.
Какво е контролна сума? fnv, md5, crc
Контролната сума (или „подпис“) е уникален номер, свързан с някакъв текст и/или функция за изчисляването му. Функцията за изчисляване на контролни суми може да има няколко цели: например „неразбиваема“ (намалява до минимум вероятността стойността на контролната сума да съвпадне с оригиналния текст) или „неповтаряща се“ (намалява до минимум вероятността два различни текста да имат една и съща контролна сума). Има обширна литература за алгоритми за изчисляване на контролна сума, тук ще спомена най-известните: fnv, md5, crc. Обикновено няма значение кой да изберете, но във всеки случай при избора на алгоритъм добрата производителност може да се счита за негова положителна страна.
Херпес зостер
Най-известният начин за справяне с почти дубликати при търсения в мрежата, елегантно въведен от Андрей Броудър през 1997 г., е методът „херпес зостер“. Очевидно, за да се увеличи вероятността контролната сума да не се промени в резултат на малки промени в текста, можете да опитате да изберете няколко подниза от текста. Шингъл (от англ. shingle - мащаб, плочка) е подниз от текст, който се използва за изчисляване на контролната сума.
Можете да изберете такива поднизове по различни начини. Първо, можете да предприемете различна стъпка, например: символ, дума, изречение. Второ, решете как трябва да вървят - припокриване (точно така се получават „херпес зостер“) или от край до край. Трето, трябва да разберете какворазмерът трябва да бъде поднизове (избраният размер трябва да минимизира произволните повторения, тоест трябва да е достатъчно голям, но в същото време да остане достатъчно малък, така че типичните текстови промени да не унищожават всички подписи, не давам конкретни числа тук, по очевидни причини те не трябва да се рекламират), и дали да ги направя фиксиран размер. И, четвърто, тъй като в текста има твърде много възможни подредове, трябва да решите кои да запомните и кои да изхвърлите.
Дупе
Ако запомните контролни суми за редове с фиксирана дължина, които вървят от край до край, тогава вмъкването и изтриването на един знак (особено в началото на текста) ще ги унищожи всички, независимо как ги избирате. Това е най-лошият вариант.
Ако обаче отмените фиксирането на дължината и преброите поднизовете от една характерна точка в текста до друга (например от буквата „u“ до буквата „u“ или от двубуквен знак, сумата от числовите стойности на знаците (буквите), които са кратни на 50, до следващия), вмъкването (или изтриването) най-вероятно ще унищожи само плочката, където се е случило.
Когато се знае, че документът се променя, макар и силно, но на малък брой места, успешно се използва този тип подпис. Например: прехвърляне на HTML файлове или синхронизиране на хранилището на изходния код и др.
За съжаление, в този вариант има твърде много подписи, освен ако, разбира се, не изберем характерни точки, които са средно далеч една от друга. Но след това редовете стават твърде големи и алгоритъмът е твърде нестабилен за малки промени в текста. За вероятностно сравнение на два документа все още е необходимо по някакъв начин да се намали извадката и повече за това по-късно.
Припокриване
Първоначално изглежда, че за изчисляване на контролните суми за всички редовеприпокриването е странна идея. Трябва да намалим количеството данни за сравнение, но в този случай расте ужасно? Това обаче е начинът, по който ние гарантираме, че няма да пропуснем нито един подниз от текст (с дадена дължина) и, при условие че можем да измислим стабилен начин за избор на шингли, можем много точно да идентифицираме документи, които имат съответстващи части.
Вземане на проби. Какви херпес зостер да запомните?
Класическият алгоритъм на Brodeur предлага да се избере или фиксиран брой херпес зостер с минимална стойност, или всички херпес зостер, чиято стойност се дели на малко число (10-30). В първия случай получаваме селекция с фиксиран размер (което понякога е удобно) и приличен набор от шингли дори за сравнително кратки документи, но ще бъде невъзможно да се прецени влагането на документи. Във втория случай броят на шинглите е пропорционален на размера на документа, т.е. той е променлив, но е възможно да се оценят такива интересни неща като влагането на документи един в друг или процентът на тяхното пресичане от набора шингли. И накрая, последният най-модерен алгоритъм генерира фиксирана извадка, чийто размер се определя от даден брой (например 85 за уеб документи) различни независими произволни функции, за всяка от които се съхранява точно една шингла, минималната по отношение на стойността на контролната сума. Този подход съчетава предимствата на предишните два.
Кратки документи. Какво може да се направи?
Какво да правим с много кратки документи, за които алгоритъмът за избор на керемиди (например вторият) може изобщо да не избере подходящи? Или изберете твърде малко? Знам две алтернативни решения: едно от тях: зациклете текста на документа, тоест виртуално продължете началото му след края, за да постигнете необходимото количествохерпес зостер дори при такива условия. Вторият подход, използван в Yandex-Mail, е използването на извадка, чийто размер има логаритмична зависимост от размера на документа.
Супершинда
Ако за всяка буква е избрана повече от една шингла, ние сме изправени пред проблема с идентифицирането на документи, които имат само няколко съвпадащи шингли. Без значение как намаляваме броя на херпес зостер, все още остава нетривиално количество работа: има много данни, дори ако твърде редките и твърде честите херпес зостер се изхвърлят; няма незабавно работеща заявка за идентифициране на документ и т.н.
Следователно, на практика, още една контролна сума, така наречената „супершинда“, често се изчислява върху набор от документни шингли. Очевидно в този случай само документи с напълно съвпадащи комплекти керемиди ще се считат за съвпадащи. Въпреки това, с правилния избор на алгоритъма и неговите параметри, това може да е достатъчно, за да работи добър детектор за поща. Задачата ще се сведе до изчисляване само на едно число и намирането му в най-простата база данни.
Замяна на Supershingle: Лексикални подписи
Не е необходимо да търсите много подобни документи по контролни суми и трудни поднизове. Лексикалните (базирани на думи) методи също работят доста успешно (поне при задачи за търсене в мрежата). Цялото разнообразие от тези методи сега е разделено на два класа, локални и глобални лексикални подписи.
Ако местните сигнатури разглеждат документа изолирано от колекцията и се опитват да извлекат няколко характерни думи само въз основа на тяхната статистика в самия документ - TF (типичен пример: вземете 5-те най-често срещани думи в документа, по-дълги от пет букви, и ги подредете в низходяща честота), тогава глобалните или се опитват да анализиратдокумент, вземете предвид информацията за глобалната статистика на думата - IDF или като цяло изберете ключови думи въз основа единствено на вече съществуващия обърнат индекс (вижте метода Yandex). За работата на глобалните методи е необходимо по някакъв начин да се изчисли глобалната статистика на думите, което е напълно възможно в интензивна анти-спам система, например в рамките на байесовия подход.