Исследование ускоренного поиска близких текстовых последовательностей с помощью векторных представлений
Gespeichert in:
| Datum: | 2008 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/44195 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Исследование ускоренного поиска близких текстовых последовательностей с помощью векторных представлений / А.М. Соколов // Кибернетика и системный анализ. — 2008. — № 4. — С. 32-47. — Бібліогр.: 27 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-44195 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-441952013-05-27T03:10:39Z Исследование ускоренного поиска близких текстовых последовательностей с помощью векторных представлений Соколов, А.М. Кибернетика 2008 Article Исследование ускоренного поиска близких текстовых последовательностей с помощью векторных представлений / А.М. Соколов // Кибернетика и системный анализ. — 2008. — № 4. — С. 32-47. — Бібліогр.: 27 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/44195 004.032.26 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Кибернетика Кибернетика |
| spellingShingle |
Кибернетика Кибернетика Соколов, А.М. Исследование ускоренного поиска близких текстовых последовательностей с помощью векторных представлений Кибернетика и системный анализ |
| format |
Article |
| author |
Соколов, А.М. |
| author_facet |
Соколов, А.М. |
| author_sort |
Соколов, А.М. |
| title |
Исследование ускоренного поиска близких текстовых последовательностей с помощью векторных представлений |
| title_short |
Исследование ускоренного поиска близких текстовых последовательностей с помощью векторных представлений |
| title_full |
Исследование ускоренного поиска близких текстовых последовательностей с помощью векторных представлений |
| title_fullStr |
Исследование ускоренного поиска близких текстовых последовательностей с помощью векторных представлений |
| title_full_unstemmed |
Исследование ускоренного поиска близких текстовых последовательностей с помощью векторных представлений |
| title_sort |
исследование ускоренного поиска близких текстовых последовательностей с помощью векторных представлений |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2008 |
| topic_facet |
Кибернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/44195 |
| citation_txt |
Исследование ускоренного поиска близких текстовых последовательностей с помощью векторных представлений / А.М. Соколов // Кибернетика и системный анализ. — 2008. — № 4. — С. 32-47. — Бібліогр.: 27 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT sokolovam issledovanieuskorennogopoiskablizkihtekstovyhposledovatelʹnostejspomoŝʹûvektornyhpredstavlenij |
| first_indexed |
2025-07-04T02:35:56Z |
| last_indexed |
2025-07-04T02:35:56Z |
| _version_ |
1836682110790795264 |
| fulltext |
ÓÄÊ 004.032.26
À.Ì. ÑÎÊÎËÎÂ
ÈÑÑËÅÄÎÂÀÍÈÅ ÓÑÊÎÐÅÍÍÎÃÎ ÏÎÈÑÊÀ ÁËÈÇÊÈÕ
ÒÅÊÑÒÎÂÛÕ ÏÎÑËÅÄÎÂÀÒÅËÜÍÎÑÒÅÉ Ñ ÏÎÌÎÙÜÞ
ÂÅÊÒÎÐÍÛÕ ÏÐÅÄÑÒÀÂËÅÍÈÉ
Êëþ÷åâûå ñëîâà: aïïðîêñèìàöèÿ ðàññòîÿíèÿ ðåäàêòèðîâàíèÿ, ïðèáëèæåííûé
ïîèñê áëèæàéøåãî ñîñåäà, íåéðîñåòåâûå èíôîðìàöèîííûå òåõíîëîãèè, îáíàðó-
æåíèå ñïàìà, ïîèñê äóáëèêàòîâ.
1. ÂÂÅÄÅÍÈÅ
Âî ìíîãèõ ïðèêëàäíûõ çàäà÷àõ ðàçíûõ ïðåäìåòíûõ îáëàñòåé ñóùåñòâóåò íåîá-
õîäèìîñòü ñðàâíåíèÿ äëèííûõ ñèìâîëüíûõ ïîñëåäîâàòåëüíîñòåé. Ïðèìåðàìè òà-
êèõ îáëàñòåé ÿâëÿþòñÿ âåá-ïîèñê, áîëüøèå ñèñòåìû äîêóìåíòîîáîðîòà [1], ãåíå-
òèêà [2].
Äëÿ ñðàâíåíèÿ ïîñëåäîâàòåëüíîñòåé íåîáõîäèìî çàäàòüñÿ ìåòðèêîé, êîòîðàÿ
äîëæíà áûòü àäåêâàòíîé çàäà÷å è ýôôåêòèâíî âû÷èñëèìà. Ïåðâîìó óñëîâèþ ÷àñòî
óäîâëåòâîðÿåò ðàññòîÿíèå Ëåâåíøòåéíà (êëàññè÷åñêîå ðàññòîÿíèå ðåäàêòèðîâàíèÿ)
[3]. Îíî îïðåäåëÿåòñÿ ìåæäó ñèìâîëüíûìè ñòðîêàìè x è y êàê ìèíèìàëüíîå êîëè-
÷åñòâî îïåðàöèé âñòàâêè, çàìåíû è óäàëåíèÿ ñèìâîëîâ äëÿ ïðåîáðàçîâàíèÿ x â y.
Ýòè îïåðàöèè èíòåðïðåòèðóþòñÿ â çàäà÷àõ ãåíåòèêè êàê îïåðàöèè, ïðîèñõîäÿùèå
ïðè ìóòàöèÿõ è ýâîëþöèè ãåíîâ, è êàê íåêîòîðûå ñïîñîáû èñêàæåíèÿ òåêñòîâ äëÿ
íåñàíêöèîíèðîâàííîé ðåêëàìû â Èíòåðíåò èëè èñêàæåíèÿ ïðè îïòè÷åñêîì
ðàñïîçíàâàíèè òåêñòîâ â ñèñòåìàõ äîêóìåíòîîáîðîòà.
Øèðîêî èçâåñòåí êëàññè÷åñêèé àëãîðèòì âû÷èñëåíèÿ ðàññòîÿíèÿ Ëåâåíøòåé-
íà, èìåþùèé äëÿ ñòðîê äëèíîé n ñëîæíîñòü O n( )2 [4]. Ââèäó áîëüøèõ õàðàêòåð-
íûõ ðàçìåðîâ n, à òàêæå áîëüøîãî êîëè÷åñòâà ñòðîê ïðèìåíåíèå ýòîãî àëãîðèòìà â
ïåðå÷èñëåííûõ âûøå îáëàñòÿõ âåñüìà çàòðóäíèòåëüíî. Ïîýòîìó òðåáóåòñÿ âû÷èñ-
ëèòåëüíî ýôôåêòèâíàÿ îöåíêà ðàññòîÿíèÿ ðåäàêòèðîâàíèÿ [5].
 ðàáîòå [6] ðàçðàáîòàí ìåòîä îöåíêè ðàññòîÿíèÿ Ëåâåíøòåéíà íà îñíîâå âëî-
æåíèÿ ðàññòîÿíèÿ ðåäàêòèðîâàíèÿ â âåêòîðíîå ïðîñòðàíñòâî, à òàêæå ïðåäëîæåí
àëãîðèòì íàõîæäåíèÿ ïðèáëèæåííûõ áëèæàéøèõ ñòðîê íà îñíîâå ìîäèôèêàöèè
ñõåìû ëîêàëüíî-÷óâñòâèòåëüíîãî õåøèðîâàíèÿ (locality-sensitive hashing — LSH
[7]), èñïîëüçóþùåé p-ñòàáèëüíûå ðàñïðåäåëåíèÿ [8]. Îäíàêî ïðåäëîæåííûå
ìåòîäû òðåáóþò èññëåäîâàíèÿ â ýêñïåðèìåíòàõ è ïðèëîæåíèÿõ.
 íàñòîÿùåé ñòàòüå îïèñàíû ðåçóëüòàòû ÷èñëåííûõ ýêñïåðèìåíòîâ ïî ïðîâåðêå òå-
îðåòè÷åñêèõ ðåçóëüòàòîâ ïðåäëîæåííîé ñõåìû íà èñêóññòâåííûõ äàííûõ. Ðàññìàòðèâà-
åòñÿ ïðèìåíåíèå ïðåäëîæåííîãî àëãîðèòìà ïðèáëèæåííîãî íàõîæäåíèÿ áëèæàéøèõ
ñòðîê ê ñëåäóþùèì àêòóàëüíûì ïðàêòè÷åñêèì çàäà÷àì ôèëüòðàöèè äóáëèêàòîâ (â ïîèñ-
êîâûõ ìàøèíàõ, ñèñòåìàõ äîêóìåíòîîáîðîòà è äð.) è îáíàðóæåíèÿ ñïàìà, ò.å. ñîîáùå-
íèé, êàê ïðàâèëî, ðåêëàìíîãî õàðàêòåðà, ìàññîâî ðàññûëàåìûõ ëþäÿì, íå âûðàçèâøèì
æåëàíèå èõ ïîëó÷àòü (äëÿ âåá-ñòðàíèö, ýëåêòðîííîé ïî÷òû è ò.ï.).
2. ÂËÎÆÅÍÈÅ ÐÀÑÑÒÎßÍÈß ÐÅÄÀÊÒÈÐÎÂÀÍÈß
Îïèøåì ñóòü ïðåäëîæåííîãî è îáîñíîâàííîãî â ðàáîòå [6] äåòåðìèíèðîâàííîãî
è âåðîÿòíîñòíîãî âëîæåíèÿ êëàññè÷åñêîãî ðàññòîÿíèÿ ðåäàêòèðîâàíèÿ â âåêòîð-
íîå ïðîñòðàíñòâî, à òàêæå ñõåìû ïîèñêà ïðèáëèæåííûõ äóáëèêàòîâ ñèìâîëüíûõ
ñòðîê íà îñíîâå ïðåäëîæåííîãî âëîæåíèÿ.
32 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 4
© À.Ì. Ñîêîëîâ, 2008
2.1. Äåòåðìèíèðîâàííàÿ ñõåìà
Äëÿ íåêîòîðîé ñèìâîëüíîé ñòðîêè x n�� , à òàêæå ïàðàìåòðà q N� íàçîâåì
q-ãðàììîé ïîäñòðîêó äëèíîé q. Íàçîâåì âåêòîð âèäà �n q x N,
| |( ) ( { })� � 0 �
q-ãðàììíûì âåêòîðîì, ãäå êàæäîé q-ãðàììå � ��q ñîîòâåòñòâóåò ýëåìåíò âåêòî-
ðà ( ( )),� �n q x N� �{ }0 , çíà÷åíèå êîòîðîãî — ÷èñëî âõîæäåíèé � â x. Ìàíõåòåí-
íîâî ( )l1 ðàññòîÿíèå ìåæäó òàêèìè âåêòîðàìè, ò.å. ñóììà ìîäóëåé ðàçíîñòåé
çíà÷åíèé ýëåìåíòîâ âåêòîðîâ, íàçûâàåòñÿ q-ãðàììíûì ðàññòîÿíèåì [9] è îáîçíà-
÷àåòñÿ d x yq ( , ) .
Ïóñòü çàäàíû îêíî øèðèíîé w ñèìâîëîâ è äâà çíà÷åíèÿ äëèíû q-ãðàìì — q1 è
q2 , q q1 2� . Ñòðîêà x ïðåîáðàçîâûâàåòñÿ â âåêòîð �( )x êîíêàòåíàöèåé âñåõ q-ãðàì-
ìíûõ âåêòîðîâ
� �i w q w q x i i w, , , ( [ , – ])� � 1 (1)
äëÿ q q q q� � �1 1 21, , , è i n w� � �1 1, , – .
Ðàññòîÿíèåì ìåæäó òàêèìè âåêòîðàìè áóäåì ñ÷èòàòü q-ãðàììíîå ðàññòîÿíèå, è
íà åãî îñíîâàíèè îïðåäåëèì íîâîå ðàññòîÿíèå ìåæäó ñòðîêàìè x y w, �� :
d x y d x y
w q q q q q q, , , ,( , ) ( , )
1 2 1 2
� �� � � . (2)
Îáîçíà÷èì q q q�
2 1. Äëÿ ñòðîê x y n, �� îïðåäåëèì ñ èñïîëüçîâàíèåì (1)
ðàññòîÿíèå
D x y d x i i w y i i wi n w w q q
( , ) ( [ , – ], [ , – ], , – , ,
� � �� � �� �
1 1
1 2
1 1 ) / (( )( ))n w q
� �1 1 . (3)
Ïóñòü q w1 2 3� / , � � q w q� � �1 2 7 57 16 1
1 2/ (– ( ( – )) )/ , Q q q� � �( )( ), 1 2
t w q� �– 1. Â [6] ïîêàçàíî, ÷òî
åñëè ed( , ) ,x y k
2 òî D x y Qt k q n w q d( , ) ( / ( ( ))– ) / (( – )( ))� � � � �2 22 1 2 1 1 ; (4)
åñëè ed( , ) ,x y k� 1 òî D x y k w n n w d( , ) [ ( )] / ( – )� � � � �2 1 11
2
1, (5)
ãäå ed(x, y) — ðàññòîÿíèå ðåäàêòèðîâàíèÿ.
Ïðè óñëîâèè d d2 1
÷åì ìåíüøå ðàçíîñòü ìåæäó k1 è k2 , òåì òî÷íåå ìîæíî
àïïðîêñèìèðîâàòü ed( , )x y ïðè èçâåñòíîì D x y( , ). Ïîëîæèì w n� � . Òîãäà ïîêàçà-
òåëü ðîñòà w, îáåñïå÷èâàþùèé íàèáîëüøóþ òî÷íîñòü àïïðîêñèìàöèè, äîñòèãàåòñÿ
ïðè � � 05. . Ïðè ýòîì k k n2 1
1 2� �( )/ , âðåìÿ ïîñòðîåíèÿ âåêòîðîâ �( )� ðàâíî
O n( )/3 2 , à èõ ðàçìåðíîñòü — O n( )/5 4 .
Ïîëó÷åííûå îöåíêè âðåìåíè ïîñòðîåíèÿ è ðàçìåðíîñòè ïîëó÷àåìûõ âåêòîðîâ â äå-
òåðìèíèðîâàííîé ñõåìå ñëèøêîì âåëèêè äëÿ ýôôåêòèâíîãî èñïîëüçîâàíèÿ íà ïðàêòèêå.
Ïîýòîìó â [6] áûëà ïðåäëîæåíà ðàíäîìèçàöèÿ ýòîé ñõåìû, ïðèìåíèìàÿ äëÿ çàäà÷è ïî-
èñêà ïðèáëèæåííî áëèæàéøèõ ñîñåäåé è ìåíåå òðåáîâàòåëüíàÿ ê ðåñóðñàì.
2.2. Ðàíäîìèçèðîâàííàÿ ñõåìà
Ïóñòü âåêòîð �
w q q
i x
, ,
( )
1 2
ÿâëÿåòñÿ êîíêàòåíàöèé q-ãðàììíûõ (îò q1 äî q2 ) âåêòî-
ðîâ (1) ïîäñòðîêè x i i w[ , – ]� 1 äëèíîé w, ãäå i âûáðàíî ñëó÷àéíî è ðàâíîâåðîÿòíî
èç ìíîæåñòâà âîçìîæíûõ ïîçèöèé îêíà øèðèíîé w i n w: ,... , – .� �1 1 Ðàçìåðíîñòü
âåêòîðà �
w q q
i x
, ,
( )
1 2
ðàâíà � �q q q
q
� �1 2, , | | .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 4 33
Ïóñòü �
i — ñëó÷àéíûé âåêòîð òàêîé æå ðàçìåðíîñòè, êàê è �
w q q
i x
, ,
( )
1 2
, ñ ýëå-
ìåíòàìè, âûáðàííûìè ñëó÷àéíî èç ðàñïðåäåëåíèÿ Êîøè p x x( ) ( ( ))� �
� 1 2 1. Ïî-
ñòðîèì äëÿ ñòðîêè x õåø-âåêòîð ðàçìåðíîñòüþ K h x h x h x h xK: ( ) ( ( ), ( ),... , ( ))� 1 2 ,
ãäå
� �h x x b ri w q q
i
i i( ) (( ( ), ) ) /
, ,
� �� �
1 2
, (6)
r è bi — äåéñòâèòåëüíûå ÷èñëà, bi âûáðàíî ñëó÷àéíî è ðàâíîâåðîÿòíî èç äèàïà-
çîíà [ , ]0 r .
Åñëè îïðåäåëèòü øàð B q k x q x kn( , ) { | ( , )� � �� ed }, òî ñåìåéñòâî
H h Xn� �{ : }� (ãäå X — íåêîòîðîå êîíå÷íîå èëè ñ÷åòíîå ìíîæåñòâî çíà÷åíèé)
íàçûâàåòñÿ [7] ( , , , )k k p p1 2 1 2 -÷óâñòâèòåëüíûì èëè êðàòêî ëîêàëüíî-÷óâñòâèòåëü-
íûì, åñëè äëÿ ëþáûõ x y n, �� è ëþáîé íåçàâèñèìî è ðàâíîâåðîÿòíî âûáðàííîé
õåø-ôóíêöèè h H� âûïîëíÿþòñÿ óñëîâèÿ:
åñëè x B y k� ( , )1 , òî Prob[ ( ) ( )]h x h y p�
1, (7)
åñëè x B y k� ( , )2 , òî Prob[ ( ) ( )]h x h y p� � 2 . (8)
Äëÿ òîãî ÷òîáû ñåìåéñòâî H ïîçâîëÿëî îòëè÷èòü «áëèçêèå» ñòðîêè îò «äàëü-
íèõ», íåîáõîäèìî âûïîëíåíèå óñëîâèÿ k k1 2� , ò.å. áëèçêàÿ ñòðîêà x äîëæíà íàõî-
äèòüñÿ áëèæå ê y, ÷åì äàëüíÿÿ, ïðè ýòîì p p2 1� , ò.å. áëèçêèå ñòðîêè äîëæíû âû-
çûâàòü êîëëèçèþ õåø-ôóíêöèé ñ áîëüøåé âåðîÿòíîñòüþ, ÷åì äàëüíèå.
 [6] äîêàçûâàåòñÿ, ÷òî (6) åñòü ëîêàëüíî-÷óâñòâèòåëüíîé ôóíêöèåé (ïðè
w n� 2 3/ , r w� è q q Q t1 , , , òàêèõ, êàê â äåòåðìèíèðîâàííîé ñõåìå) è íà åå îñíîâå
ìîæíî ïîñòðîèòü ïðîöåäóðó ïîèñêà áëèæàéøèõ ñòðîê, âîñïîëüçîâàâøèñü ñëåäóþ-
ùåé îáùåé ñõåìîé èç [9, 10].
Àëãîðèòì ïîèñêà áëèæàéøåé ñòðîêè ñ ïîìîùüþ LSH. Ïóñòü èìååòñÿ áàçà
P ñòðîê îäèíàêîâîé äëèíû n. Íåîáõîäèìî íà çàïðîñ q n�� âîçâðàòèòü ïðèáëèæåí-
íîãî áëèæàéøåãî ñîñåäà — ñòðîêó, íàõîäÿùóþñÿ â øàðå B q k( , ).2 Âñå ñòðîêè x P�
çàïîìèíàþòñÿ â ÿ÷åéêàõ ïàìÿòè ñëåäóþùèì îáðàçîì.
1. Ïî ôîðìóëå (6) äëÿ êàæäîé ñòðîêè x áàçû P ãåíåðèðóåòñÿ L K-ìåðíûõ ñëó-
÷àéíûõ õåø-âåêòîðîâ h x h x h x h xj j j
K
j( ) ( ( ), ( ),... , ( ))�
1 2
, j L� 1,... , .
2. Äëÿ êàæäîãî óíèêàëüíîãî õåø-âåêòîðà, ïîëó÷åííîãî èç âñåõ ñòðîê áàçû
h xj ( ) , j L x P� �1,... , , , ñîçäàåòñÿ ÿ÷åéêà ïàìÿòè. Îáùåå ÷èñëî ÿ÷ååê C L P� � | |.
3. Êàæäàÿ ñòðîêà áàçû P ñòàâèòñÿ â ñîîòâåòñòâèå òåì ÿ÷åéêàì, õåø-âåêòîðû
êîòîðûõ åþ ïðîäóöèðóþòñÿ.
Äëÿ íàõîæäåíèÿ ïðèáëèæåííîãî áëèæàéøåãî ñîñåäà ê ïîñòóïèâøåé
ñòðîêå q n�� :
1) ôîðìèðóåòñÿ L åå õåø-âåêòîðîâ;
2) ïðîñìàòðèâàþòñÿ ÿ÷åéêè, õåø-âåêòîðû êîòîðûõ ïîëíîñòüþ ñîâïàäàþò ñî
ñôîðìèðîâàííûìè äëÿ q, ñîîòâåòñòâóþùèå êàæäîìó õåø-âåêòîðó h q h qj j( ) ( ( ),�
1
h q h qj
K
j
2
( ),... , ( )) , j L� 1,... , ;
3) ñîñòàâëÿåòñÿ ñïèñîê S ñîäåðæàùèõñÿ â ïðîñìîòðåííûõ ÿ÷åéêàõ ñòðîê èç
áàçû P. Òàê êàê îäíà è òà æå ñòðîêà áàçû P ìîæåò âñòðå÷àòüñÿ â S íåñêîëüêî ðàç, òî
ýòîò ñïèñîê ìîæíî ïðåäñòàâèòü â âèäå ìóëüòèìíîæåñòâà.
Ïðîöåäóðà çàêàí÷èâàåòñÿ èëè ïî ïðîñìîòðó âñåõ ÿ÷ååê, ñîîòâåòñòâóþùèõ
õåø-âåêòîðàì h qj ( ), j L� 1,... , , èëè êîãäà ðàçìåð ñïèñêà S äîñòèãíåò 2L .
 [6] îïðåäåëÿþòñÿ çíà÷åíèÿ âåðîÿòíîñòåé p1 è p2 è äîêàçûâàåòñÿ ñëåäóþùàÿ
òåîðåìà.
34 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 4
Òåîðåìà 1. Ïðè îïèñàííîì ïîñòðîåíèè âåêòîðîâ, çíà÷åíèè � � log ( p p1 2/ ) è
ïðè çíà÷åíèÿõ
K Pp� log1 2/ | | , (9)
L P�| |� (10)
àëãîðèòì ïîèñêà âûäàñò â S ñ âåðîÿòíîñòüþ áîëüøåé, ÷åì 1/2, ñòðîêó y òàêóþ,
÷òî ed( , )x y k� 2 , ãäå k O zn n2
1 3� ( ln )/ , z — ïàðàìåòð, êîòîðûé âëèÿåò íà çíà÷å-
íèå k2 è çíà÷åíèÿ âåðîÿòíîñòåé p p1 2, .
Äëÿ ýêñïåðèìåíòîâ, îïèñûâàåìûõ íèæå, áûëè ïðèíÿòû ïàðàìåòðû
k z1 1 1 01� �, . . Îïèñàííîå õåøèðîâàíèå ñòðîêè ìîæåò áûòü òàêæå âûïîëíåíî â
âèäå íåéðîñåòåâîãî ðàñïðåäåëåííîãî ïðåäñòàâëåíèÿ [10].
Ðåàëèçàöèÿ ïîèñêà áëèæàéøåé ñòðîêè ñ ïîìîùüþ LSH-ëåñà. Äëÿ ïðîãðàì-
ìíîé ðåàëèçàöèè îïèñàííîé ïðîöåäóðû LSH çäåñü èñïîëüçóåòñÿ ìîäèôèêàöèÿ îïè-
ñàííîé ñõåìû LSH, íàçûâàåìàÿ LSH-ëåñ, êîòîðàÿ ïîçâîëÿåò íàõîäèòü áëèæàéøèõ
ñîñåäåé áåç îáíîâëåíèÿ õåø-âåêòîðîâ ïðè èçìåíåíèè ðàçìåðà áàçû P èëè ïàðàìåò-
ðà k2 [11].
Äëÿ êàæäîãî j L� 1,... , âñå õåø-âåêòîðû h pj ( ) âñåõ ñòðîê p áàçû P õðàíÿòñÿ â
âèäå îòäåëüíîãî ïðåôèêñíîãî äåðåâà T j ãëóáèíîé äî K óðîâíåé (êîðåíü èìååò ãëó-
áèíó 0, ëèñòüÿ — ãëóáèíó K). Óçëû äåðåâà ñîîòâåòñòâóþò çíà÷åíèÿì ýëåìåíòîâ
õåø-âåêòîðà è ñîäåðæàò ññûëêè íà ñòðîêè, õåø-âåêòîðû êîòîðûõ ñîîòâåòñòâóþò
ïóòè îò êîðíÿ äåðåâà ê äàííîìó óçëó. Ëèñòüÿ äåðåâüåâ ñîîòâåòñòâóþò ÿ÷åéêàì â
îðèãèíàëüíîé ñõåìå. Òàê, åñëè â õåø-âåêòîðàõ äâóõ ñòðîê ñîâïàäàþò ïåðâûå k èõ
ýëåìåíòîâ, òî è ïåðâûå k óçëîâ íà ïóòè îò êîðíÿ äåðåâà T j äî ëèñòüåâ,
ñîîòâåòñòâóþùèõ ýòèì ñòðîêàì, òàêæå ñîâïàäàþò.
Ïðè ïîñòóïëåíèè çàïðîñà-ñòðîêè q:
— ôîðìèðóþòñÿ L åãî K-ìåðíûõ õåø-âåêòîðîâ h qj ( ) ;
— äëÿ êàæäîãî õåø-âåêòîðà h pj ( ) â T j íàõîäèòñÿ óçåë, ñîîòâåòñòâóþùèé
h pj ( ) ñ íàèáîëüøèì ÷èñëîì ñîâïàäàþùèõ ïåðâûõ ýëåìåíòîâ ýòèõ âåêòîðîâ;
— íà÷èíàÿ îò íàéäåííûõ âûøå óçëîâ, âñå L äåðåâüåâ ñèíõðîííî ïðîñìàòðèâà-
þòñÿ ïî íàïðàâëåíèþ ê êîðíþ è ñîîòâåòñòâóþùèå óêàçàííûì óçëàì ñòðîêè p äî-
áàâëÿþòñÿ â ðåçóëüòèðóþùåå ìóëüòèìíîæåñòâî S ñòðîê;
— ïîñëå òîãî, êàê âñå ñòðîêè, õåø-âåêòîðû êîòîðûõ ñîâïàäàþò íà äàííîì
óðîâíå, äîáàâëåíû â S , ïîâòîðÿåì ïðîöåäóðó äëÿ ñëåäóþùåãî (áîëåå âûñîêîãî)
óðîâíÿ, ïîêà íå äîñòèãíåì êîðíÿ èëè | |S íå ïðåâûñèò 2L .
 ðåçóëüòàòå ïîëó÷àåì ìóëüòèìíîæåñòâî S ñòðîê (êàíäèäàòîâ íà ïðèáëèæåí-
íîãî áëèæàéøåãî ñîñåäà ê q), óïîðÿäî÷åííîå â ïîðÿäêå óáûâàíèÿ ãëóáèíû óçëîâ
äåðåâà, äî êîòîðûõ ñîâïàäàëè ïåðâûå ýëåìåíòû õåø-âåêòîðîâ ñîîòâåòñòâóþùåé
ñòðîêè è çàïðîñà. Áóäåì äàëåå ïîä óðîâíåì ñòðîêè èç S ïîíèìàòü ãëóáèíó ïîñëåä-
íåãî óçëà äåðåâà, íà êîòîðîì åùå ñîâïàäàëè ïåðâûå ýëåìåíòû õåø-âåêòîðîâ
çàïðîñà è ýòîé ñòðîêè.
Ñîãëàñíî òåîðåìå 5.1 èç [11] S áóäåò ñîäåðæàòü ñ íåíóëåâîé êîíñòàíòíîé âåðî-
ÿòíîñòüþ (àíàëîãè÷íî òåîðåìå 1) ïðèáëèæåííûõ áëèæàéøèõ ñîñåäåé ê çàïðîñó q.
3. ×ÈÑËÅÍÍÎÅ ÈÑÑËÅÄÎÂÀÍÈÅ ÒÅÎÐÅÒÈ×ÅÑÊÈÕ ÎÃÐÀÍÈ×ÅÍÈÉ
3.1. Ýêñïåðèìåíòàëüíàÿ áàçà RandomStrings
Äëÿ ïðîâåðêè òåîðåòè÷åñêèõ ðåçóëüòàòîâ ïðîâåäåíû ýêñïåðèìåíòû ñ äåòåðìèíè-
ðîâàííîé è âåðîÿòíîñòíîé ñõåìîé íà èñêóññòâåííî ñãåíåðèðîâàííûõ äàííûõ.
Íåêîòîðàÿ (ñëó÷àéíàÿ) ñòðîêà — öåíòð q ñëó÷àéíî ðåäàêòèðîâàëàñü ñ èñïîëüçî-
âàíèåì îïåðàöèé âñòàâêè, óäàëåíèÿ è çàìåíû. Ïîëó÷åííûå ïðè òàêîì ðåäàêòèðî-
âàíèè ñòðîêè ñîñòàâëÿëè êîëëåêöèþ ñòðîê. Ïîñêîëüêó îáùåå ÷èñëî îïåðàöèé íà-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 4 35
ìíîãî ìåíüøå äëèíû ñòðîêè, à ïîñ÷èòàòü ðàññòîÿíèå ðåäàêòèðîâàíèÿ íå ïðåä-
ñòàâëÿåòñÿ âîçìîæíûì ââèäó âû÷èñëèòåëüíîé ñëîæíîñòè, òî ïîëîæèì, ÷òî
ðàññòîÿíèå ðåäàêòèðîâàíèÿ ïðèáëèçèòåëüíî ðàâíî ñóììå êîëè÷åñòâ èñêàæåíèé.
Àíàëîãè÷íîå äîïóùåíèå áûëî ïðèíÿòî â [12].  äàëüíåéøåì áóäåì ññûëàòüñÿ
íà ýòîò íàáîð ñòðîê êàê íà RandomStrings.
3.2. Äåòåðìèíèðîâàííàÿ ñõåìà
Ïðîâåðêà òåîðåòè÷åñêèõ îãðàíè÷åíèé. Ýêñïåðèìåíòàëüíîå èññëåäîâàíèå òîãî,
ïîïàäàåò ëè âåëè÷èíà ðàññòîÿíèÿ D x y( , ) èç (3) â èíòåðâàë (4) è (5), âûïîëíÿ-
ëîñü äëÿ ñòðîê èç áàçû RandomStrings. Íà ðèñ. 1 ïðèâåäåíû ìèíèìàëüíûå (êðåñ-
òèêè) è ìàêñèìàëüíûå (íîëèêè) ýêñïåðèìåíòàëüíûå çíà÷åíèÿ âåëè÷èíû D x y( , )
äëÿ êàæäîãî èç çíà÷åíèé ðàññòîÿíèÿ ðåäàêòèðîâàíèÿ ed ( , )x y äëÿ n � 5000 è
n � 10000 . Ãðàôèê ñòàíîâèòñÿ ïîëîãèì âáëèçè ìàêñèìàëüíî âîçìîæíîãî çíà÷åíèÿ
ðàññòîÿíèÿ D x y w q q( , ) [ ( )– – ]� �2 1 2 1 (40 äëÿ n � 5000 è 58 äëÿ n � 10000) , êîãäà
â êàæäîì îêíå èìååòñÿ 2 1( – )w q � ðàçëè÷íûõ q-ãðàìì äëÿ q q q q� � �1 1 21, , , .
Òåîðåòè÷åñêèå çíà÷åíèÿ âåðõíåé (4) è íèæíåé (5) ãðàíèö D x y( , ) èçîáðàæåíû ñî-
îòâåòñòâåííî ñïëîøíîé è ïóíêòèðíîé òîíêèìè ëèíèÿìè. Âèäíî, ÷òî ýêñïåðè-
ìåíòàëüíûå äàííûå ñîîòâåòñòâóþò òåîðåòè÷åñêèì îöåíêàì.
3.3. Ðàíäîìèçèðîâàííàÿ ñõåìà
Ïðîâåðêà òåîðåòè÷åñêèõ îãðàíè÷åíèé. Êàê è äëÿ äåòåðìèíèðîâàííîãî âàðèàíòà
ñõåìû, íà èñêóññòâåííî ñãåíåðèðîâàííûõ ñòðîêàõ ðàçíîé äëèíû äëÿ ðàíäîìèçèðî-
âàííîãî âàðèàíòà ýêñïåðèìåíòàëüíî ïðîâåðÿëîñü, ïîïàäàþò ëè òåîðåòè÷åñêè ïðåä-
ñêàçàííûå çíà÷åíèÿ âåðîÿòíîñòåé pcol êîëëèçèè õåø-ôóíêöèè (6) â ïðåäåëû (7)
è (8). Íà ðèñ. 2 ïðèâåäåíû ýêñïåðèìåíòàëüíî ïîëó÷åííûå âåðîÿòíîñòè ñîâïàäåíèÿ
çíà÷åíèé õåø-ôóíêöèè (6) äëÿ ñòðîê äëèíîé n � 1000 è n � 3000 âìåñòå ñ òåîðåòè-
÷åñêèìè òî÷êàìè âåðõíåé (íîëèêè) è íèæíåé (êðåñòèêè) ãðàíèö. Âèäíî, ÷òî ýòè
ýêñïåðèìåíòàëüíûå äàííûå òàêæå ñîîòâåòñòâóþò òåîðåòè÷åñêèì îöåíêàì.
Âûáîð çíà÷åíèÿ L è äîïîëíèòåëüíàÿ ôèëüòðàöèÿ. Ïîñêîëüêó íåîáõîäèìûå
ðåñóðñû ðàñòóò ëèíåéíî îòíîñèòåëüíî L , íà ïðàêòèêå çíà÷åíèÿ L èç (9) îêàçûâàþò-
ñÿ ñëèøêîì âåëèêè [11]. Îäíàêî ïðè èñïîëüçîâàíèè ìåíüøèõ çíà÷åíèé íå ãàðàíòè-
ðóåòñÿ, ÷òî â âîçâðàùåííîå ìóëüòèìíîæåñòâî S ïîïàäåò õîòÿ áû îäíà ñòðîêà y òà-
êàÿ, ÷òî ed( , y)q k� 2 . Ñëåäóþùèå ýêñïåðèìåíòû âûïîëíÿëèñü äëÿ ïðîâåðêè òîãî,
êàê âëèÿåò íà «êà÷åñòâî» ìóëüòèìíîæåñòâà S âûáîð ìåíüøèõ (÷åì òåîðåòè÷åñêèå)
çíà÷åíèé L , à òàêæå äîïîëíèòåëüíàÿ ôèëüòðàöèÿ ìóëüòèìíîæåñòâà S , êîòîðîé
ïðåäïîëîæèòåëüíî ìîæíî îòñå÷ü ñòðîêè, ãäå ed( , )q y k
2 (false positives).
36 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 4
Ðèñ. 1. Òèïè÷íàÿ çàâèñèìîñòü ðàññòîÿíèÿ D x y( , ) îò ed ( , )x y äëÿ n � 5000 (à) è n � 10000 (á) ñèìâîëîâ
à á
ed ( , )x y
D x y( , ) D x y( , )
ed ( , )x y
Ïðîâîäèëèñü ýêñïåðèìåíòû ñëåäóþùèìè ñïîñîáàìè îöåíêè êà÷åñòâà ìóëüòè-
íîæåñòâà S .
À. Ñïîñîá îöåíêè ïî çíà÷åíèþ òî÷íîñòè.
Á. Ñïîñîá îöåíêè ïî óïîðÿäî÷åííîñòè ìóëüòèìíîæåñòâà S îòíîñèòåëüíî èç-
âåñòíîãî ýòàëîíà.
Ýêñïåðèìåíò ïî îöåíêå êà÷åñòâà S ñîãëàñíî çíà÷åíèþ òî÷íîñòè. Òðàäèöè-
îííî â ñèñòåìàõ ïîèñêà äëÿ èññëåäîâàíèÿ êà÷åñòâà ìíîæåñòâà äîêóìåíòîâ, âîçâðà-
ùàåìîãî íà çàïðîñ, àíàëèçèðóåòñÿ êîìïðîìèññ ìåæäó êîëè÷åñòâîì ðåëåâàíòíûõ
òåêñòîâ (true positives) è êîëè÷åñòâîì íåðåëåâàíòíûõ òåêñòîâ (false positives). Äëÿ
ýòîãî îïðåäåëÿþòñÿ âåëè÷èíû òî÷íîñòè p (îòíîøåíèå êîëè÷åñòâà ðåëåâàíòíûõ çà-
ïðîñó âîçâðàùåííûõ äîêóìåíòîâ ê îáùåìó ÷èñëó âîçâðàùåííûõ äîêóìåíòîâ) è
ïîëíîòû r (îòíîøåíèå êîëè÷åñòâà ðåëåâàíòíûõ çàïðîñó âîçâðàùåííûõ äîêóìåíòîâ
ê îáùåìó ÷èñëó ðåëåâàíòíûõ äîêóìåíòîâ). Ýòè âåëè÷èíû èçîáðàæàþòñÿ îáû÷íî íà
ãðàôèêàõ çàâèñèìîñòè òî÷íîñòè îò ïîëíîòû [13].
 íàñòîÿùåé ñòàòüå äàííûé ïîäõîä îêàçûâàåòñÿ íåèíôîðìàòèâíûì, ïîñêîëüêó
ðàññìàòðèâàåìàÿ çàäà÷à ïîèñêà ïðèáëèæåííîãî áëèæàéøåãî ñîñåäà ïîäðàçóìåâàåò
íàõîæäåíèå îäíîãî ñîñåäà, à íå ìíîæåñòâà ñîñåäåé. Ïîýòîìó îòíîøåíèå (ïîëíîòà)
| ( , ) | / | ( , ) |B q k P S B q k P2 2� � � íåèíôîðìàòèâíî.
Ñèòóàöèÿ ñ íåèíôîðìàòèâíîñòüþ ïîëíîòû âîçíèêàåò è â îöåíêå êà÷åñòâà ïî-
èñêîâûõ ñèñòåì: äëÿ ïîëüçîâàòåëÿ âñå ìíîæåñòâî âîçâðàùåííûõ ðåçóëüòàòîâ íå
ïðåäñòàâëÿåò èíòåðåñà, îí îáû÷íî îãðàíè÷èâàåòñÿ ïðîñìîòðîì òîëüêî ïåðâûõ ñòðà-
íèö ðåçóëüòàòîâ [14].  òàêèõ ñëó÷àÿõ âìåñòî òî÷íîñòè è ïîëíîòû îáû÷íî èñïîëü-
çóþò õàðàêòåðèñòèêó òî÷íîñòè íà óðîâíå n (precision at n P n/ @ ) [15], âû÷èñëÿåìóþ
êàê òî÷íîñòü íà îãðàíè÷åííîì ïåðâûìè n ðåçóëüòàòàìè ìíîæåñòâå.  ðàññìàòðèâà-
åìîì ñëó÷àå ýòîò óðîâåíü åñòåñòâåííî îãðàíè÷åí ðàçìåðîì ìóëüòèìíîæåñòâà S è
òî÷íîñòü íà óðîâíå | |S îïðåäåëÿåòñÿ êàê | ( , ) |/| |B q k P S S2 � � .
×òîáû íå âíîñèòü ñìåùåíèÿ â îöåíêó òî÷íîñòè íà óðîâíå | |S ââèäó íåîäèíàêî-
âîãî êîëè÷åñòâà ñòðîê âíóòðè è âíå øàðà B q k( , )2 è ðàçëè÷íîãî êîëè÷åñòâà ñòðîê
íà îïðåäåëåííîì ðàññòîÿíèè îò q, ìû îòîáðàëè èç íàáîðà RandomStrings (ðàçä. 3.1)
2200 ñòðîê äëèíîé 1000 ñèìâîëîâ (ïðè ýòîì k2 126� ) òàêèì îáðàçîì, ÷òî ÷èñëî
ñòðîê, ïðèíàäëåæàùèõ B q k( , )2 , ñîñòàâëÿëî ïîëîâèíó îò îáùåãî ÷èñëà ñòðîê è
êîëè÷åñòâî ñòðîê äëÿ êàæäîãî çíà÷åíèÿ ðàññòîÿíèÿ îò öåíòðà q íå ïðåâûøàëî 10.
Ïîëó÷åííîå ìíîæåñòâî P ñîäåðæàëî ñòðîêè, íàõîäÿùèåñÿ îò öåíòðà q íà
ðàññòîÿíèè ðåäàêòèðîâàíèÿ îò 10 äî 248.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 4 37
Ðèñ. 2. Çàâèñèìîñòü ýêñïåðèìåíòàëüíûõ çíà÷åíèé âåðîÿòíîñòè êîëëèçèè õåø-ôóíêöèé h xi ( ) è h yi ( ) îò
ðàññòîÿíèÿ ðåäàêòèðîâàíèÿ ìåæäó ñòðîêàìè äëèíîé 1000 (à) è 3000 (á) ñèìâîëîâ
à áed ( , )x y ed ( , )x y
pcolpcol
Ìíîæåñòâî P áûëî çàïîìíåíî â LSH-ëåñå ñ ïîìîùüþ ðàíäîìèçèðîâàííîé ñõå-
ìû èç ï. 2.2. Íà âõîä ïðîöåäóðû ïîèñêà ïðèáëèæåííîãî áëèæàéøåãî ñîñåäà ïîäà-
âàëñÿ çàïðîñ q. Ïî ïîëó÷åííîìó íà âûõîäå ïðè êàæäîì çàïðîñå ìíîæåñòâó
S S L(| | )
4 âû÷èñëÿëàñü òî÷íîñòü íà óðîâíÿõ 0 5. L (ãäå L — ÷åòíîå), L L L L, , ,2 3 4 .
Çíà÷åíèÿ òî÷íîñòåé óñðåäíÿëèñü ïî 100 ñëó÷àéíûì íåçàâèñèìûì ðåàëèçàöèÿì
LSH-ëåñà. Èõ çíà÷åíèÿ è äèñïåðñèÿ � p ïðèâåäåíû â òàáë. 1.
Ïðè ìàëûõ çíà÷åíèÿ L íàáëþäàåòñÿ ìàêñèìàëüíàÿ òî÷íîñòü, ÷òî ÿâëÿåòñÿ îñî-
áåííîñòüþ ïðîöåäóðû LSH-ëåñ, âîçâðàùàþùåé ìíîæåñòâî ñòðîê S , óïîðÿäî÷åííîå
ïî ãëóáèíå óðîâíÿ. Ïðè óâåëè÷åíèè çíà÷åíèÿ L âíà÷àëå òî÷íîñòü ïàäàåò, ÷òî îáúÿñ-
íÿåòñÿ á�ëüøèìè øàíñàìè ó ñòðîê èç P B q k\ ( , )2 ïîïàñòü â S , íî â äàëüíåéøåì
òî÷íîñòü ïåðåñòàåò ñóùåñòâåííî èçìåíÿòüñÿ è îäíîâðåìåííî óìåíüøàåòñÿ äèñïåð-
ñèÿ åå çíà÷åíèé, ÷òî ïîçâîëÿåò ãîâîðèòü î ñòàáèëèçàöèè çíà÷åíèé òî÷íîñòè.
Àíàëîãè÷íûé ýôôåêò íàáëþäàåòñÿ ïðè óâåëè÷åíèè | |S . Òàêèì îáðàçîì, íà ïðàêòè-
êå äîñòàòî÷íî îãðàíè÷èòüñÿ çíà÷åíèåì L , ðàâíûì íåñêîëüêèì äåñÿòêàì (íàïðèìåð,
30 èëè 40). Ýòî ïîçâîëÿåò ïîëó÷èòü ïðèåìëåìûé óðîâåíü òî÷íîñòè è ñýêîíîìèòü
ðåñóðñû. Çíà÷åíèå | |S ìîæíî çàôèêñèðîâàòü, íàïðèìåð, íà òåîðåòè÷åñêè ðåêîìåí-
äîâàííîì çíà÷åíèè 2L .
Ýêñïåðèìåíò ïî îöåíêå óïîðÿäî÷åííîñòè ìóëüòèìíîæåñòâ. Èññëåäóåì, íà-
ñêîëüêî ïîðÿäîê ñòðîê â S ñîîòâåòñòâóåò ðåàëüíîìó óïîðÿäî÷åíèþ ýòèõ æå
ñòðîê — ïî ðàññòîÿíèþ ðåäàêòèðîâàíèÿ äî q. Îáîçíà÷èì S � ìóëüòèìíîæåñòâî çíà-
÷åíèé ðàññòîÿíèÿ ðåäàêòèðîâàíèÿ ñòðîê èç S äî q S x q x S: { , | }.� � �ed ( )
Äëÿ ñðàâíåíèÿ óïîðÿäî÷åííûõ ìóëüòèìíîæåñòâ âîçüìåì çà îñíîâó îáîáùåí-
íîå ðàññòîÿíèå Êýíäàëëà [16], êîòîðîå ïîçâîëÿåò ñðàâíèâàòü óïîðÿäî÷åííûå ìíî-
æåñòâà, ââîäÿ ðàçëè÷íûå øòðàôû çà íàõîæäåíèå ýëåìåíòîâ â ðàçíûõ îòíîñèòåëü-
38 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 4
Ò à á ë è ö à 1
L
Çíà÷åíèå òî÷íîñòè íà óðîâíå | |S äëÿ
| | .S L� 0 5 � p, . L0 5 | |S L� � p, L1 | |S L� 2 � p, L2 | |S L� 3 � p, L3 | |S L� 4 � p, L4
1 0.950 0.048 0.945 0.029 0.927 0.025 0.893 0.031
2 0.930 0.065 0.895 0.056 0.853 0.054 0.825 0.032 0.810 0.028
3 0.885 0.050 0.816 0.035 0.784 0.030 0.770 0.025
4 0.855 0.071 0.842 0.041 0.810 0.031 0.777 0.023 0.757 0.021
5 0.824 0.039 0.786 0.021 0.759 0.014 0.735 0.014
6 0.853 0.052 0.797 0.040 0.782 0.025 0.760 0.019 0.730 0.014
7 0.778 0.031 0.768 0.018 0.743 0.013 0.721 0.010
8 0.846 0.038 0.791 0.024 0.755 0.016 0.729 0.013 0.724 0.010
9 0.759 0.024 0.741 0.013 0.717 0.011 0.697 0.009
10 0.860 0.030 0.787 0.024 0.749 0.015 0.722 0.009 0.689 0.008
12 0.807 0.035 0.776 0.021 0.740 0.013 0.712 0.009 0.688 0.007
14 0.821 0.028 0.770 0.018 0.740 0.010 0.716 0.007 0.682 0.006
16 0.809 0.021 0.746 0.013 0.721 0.010 0.691 0.007 0.673 0.005
18 0.845 0.019 0.765 0.014 0.719 0.008 0.686 0.005 0.665 0.004
20 0.811 0.024 0.762 0.014 0.708 0.006 0.682 0.005 0.658 0.004
íûõ ïîðÿäêàõ â ìíîæåñòâàõ M1 è M 2 . Òàê, åñëè äâà ýëåìåíòà i j M M, � �1 2 âõîäÿò
â ñðàâíèâàåìûå ìíîæåñòâà ïîä èíäåêñàìè i i j j1 2 1 2, , , , òî øòðàô u âû÷èñëÿåòñÿ ïî
ñëåäóþùèì ïðàâèëàì:
1) åñëè i i j j i i j j1 2 1 2 1 2 1 2� �
, ( , ) , òî u � 0 ;
2) åñëè i i j j i i j j1 2 1 2 1 2 1 2�
�, ( , ) , òî u � 1;
3) åñëè i i2 1( ) íå îïðåäåëåíî, ò.å. ñîîòâåòñòâóþùèé ýëåìåíò íå âõîäèò âî âòî-
ðîå (ïåðâîå) ìíîæåñòâî, à j j j j1 2 1 2�
( ) , òî u � 0 ;
4) åñëè j j2 1( ) íå îïðåäåëåíî, ò.å. ñîîòâåòñòâóþùèé ýëåìåíò íå âõîäèò âî âòî-
ðîå (ïåðâîå) ìíîæåñòâî, à i i i i1 2 1 2�
( ) , òî u � 0 ;
5) åñëè i j i j1 2 2 1, ( , ) íå îïðåäåëåíî, ò.å. êàæäûé ýëåìåíò âõîäèò ñîîòâåòñòâåííî
â ñâîå ìíîæåñòâî, òî u p� .
Ïàðàìåòð p åñòü ðåãóëèðóåìûé øòðàô çà ñèòóàöèþ, êîãäà ïåðâûé (âòîðîé)
ýëåìåíò îòñóòñòâóåò â îäíîì ìíîæåñòâå, íî ïðèñóòñòâóåò â äðóãîì è íàîáîðîò. Äëÿ
äàííûõ ýêñïåðèìåíòîâ èñïîëüçîâàëîñü p � 1.
Ðàññòîÿíèå D M MK ( , )1 2 ìåæäó ìíîæåñòâàìè ÿâëÿåòñÿ ñóììîé øòðàôîâ âñåõ
ïàð ýëåìåíòîâ M M1 2� :
D M M u i jK i j M M( , ) ( , ),1 2 1 2
� � �� . (11)
Çäåñü èçìåíåí îïèñàííûé àëãîðèòì ïîäñ÷åòà îáîáùåííîãî ðàññòîÿíèÿ Êýíäàëëà
ñ öåëüþ ïðèìåíåíèÿ åãî ê óïîðÿäî÷åííûì ìóëüòèìíîæåñòâàì (çíà÷åíèé ðàññòî-
ÿíèé ðåäàêòèðîâàíèÿ îò q äî áëèæàéøèõ ñòðîê) ñëåäóþùèì îáðàçîì. Äëÿ êàæ-
äîãî çíà÷åíèÿ ðàññòîÿíèÿ ðåäàêòèðîâàíèÿ èç S S� � �1 2 , âõîäÿùåãî õîòÿ áû â
îäíî èç ìóëüòèìíîæåñòâ, êàæäîå åãî j-å âõîæäåíèå â îáà ìóëüòèìíîæåñòâà ïî-
ñëåäîâàòåëüíî ïðåîáðàçóåòñÿ â óíèêàëüíûé àáñòðàêòíûé ýëåìåíò íîâîãî ìíî-
æåñòâà, óñëîâíî îáîçíà÷àåìûé ñèìâîëîì s j , ãäå èíäåêñ ñîîòâåòñòâóåò ïîðÿäêî-
âîìó íîìåðó, ïîä êîòîðûì îí âõîäèò â äàííîå ìíîæåñòâî.  ÷àñòíîñòè, åñëè
ýëåìåíò âõîäèò â îäíî èõ ìíîæåñòâ òîëüêî îäèí ðàç, òî åãî èíäåêñ ðàâåí åäè-
íèöå. Íàïðèìåð, èç ìíîæåñòâ S � �1 12 3 4 4 3 5{ }, , , , , , , S � �2 13 3 4 4 3 4{ }, , , , , , ïîëó÷àåì ñëå-
äóþùèå ìíîæåñòâà ýëåìåíòîâ: S M� � �1 1 1 1 1 1 2 2 11 2 3 4 4 3 5{ }, , , , , , , S M� � �2 2
={ }1 3 3 4 4 3 41 1 2 1 2 3 3, , , , , , . Ìíîæåñòâî ýëåìåíòîâ, ïîëó÷åííîå îïèñàííûì ñïîñîáîì
èç S �, áóäåì îáîçíà÷àòü M S( )� .
Òàêèì îáðàçîì, ñâåäåíà çàäà÷à ñðàâíåíèÿ óïîðÿäî÷åííûõ ìóëüòèìíîæåñòâ �S1
è �S2 ê çàäà÷å ñðàâíåíèÿ óïîðÿäî÷åííûõ ìíîæåñòâ M S( )�1 è M S( )�2 .
Êàê è â ýêñïåðèìåíòå ïî âû÷èñëåíèþ òî÷íîñòè íà óðîâíå | |S (ñì. ï. A) êîëè-
÷åñòâî ñòðîê â S , âîçâðàùàåìûõ ïðîöåäóðîé LSH-ëåñ è ôèãóðèðóþùåå â îïèñàíèè
àëãîðèòìà êàê 2L , áûëî ïåðåìåííûì, ò.å. àëãîðèòì âîçâðàùàë óêàçàííîå êîëè÷åñò-
âî ñòðîê, ïîëó÷åííûõ â ðåçóëüòàòå ïîäúåìà ïî LSH-äåðåâüÿì.
Èññëåäîâàíèå ïðîâåäåíî íà íàáîðå ñòðîê RandomStrings (ñì. ï. 3.1). Èñïîëüçî-
âàëèñü òå æå 2200 ñòðîê äëèíîé 1000 ñèìâîëîâ ( )k2 126� , ÷òî è â ïðåäûäóùåì
ýêñïåðèìåíòå. Ìíîæåñòâî P áûëî çàïîìíåíî â LSH-ëåñå ñ ïîìîùüþ ïðîöåäóðû,
ðàññìîòðåííîé â ï. 2.2. Íà âõîä ïðîöåäóðû ïîèñêà ïðèáëèæåííîãî áëèæàéøåãî
ñîñåäà ïîäàâàëñÿ çàïðîñ q.
Îáîçíà÷èì �X óïîðÿäî÷åííîå ïî âîçðàñòàíèþ ìóëüòèìíîæåñòâî çíà÷åíèé ðå-
àëüíûõ ðàññòîÿíèé ðåäàêòèðîâàíèÿ îò öåíòðà q äî åãî áëèæàéøèõ ñîñåäåé, à �Y —
óïîðÿäî÷åííîå â õîäå ïðîöåäóðû LSH-ëåñ ìóëüòèìíîæåñòâî çíà÷åíèé ðàññòîÿíèé
ðåäàêòèðîâàíèÿ îò öåíòðà q äî âîçâðàùåííûõ ñòðîê â õîäå ïðîöåäóðû LSH-ëåñ.
Âû÷èñëèì âûøåîïèñàííîå ðàññòîÿíèå D M X M YK ( ( ), ( ))� � èç (11) ïðè | |� �S 50 è
| |� �S 200 , ãäå ðàçìåð ìíîæåñòâà M X( )� îãðàíè÷èâàëñÿ ïî çíà÷åíèþ | ( )| | |.M Y S� � �
Ðåçóëüòàòû óñðåäíÿëèñü ïî 100 ñëó÷àéíûì íåçàâèñèìûì ðåàëèçàöèÿì
LSH-ëåñà. Íà ðèñ. 3 ïîêàçàíà çàâèñèìîñòü ðàññòîÿíèÿ D M X M YK ( ( ), ( ))� � îò êîëè-
÷åñòâà äåðåâüåâ L â ëåñå äëÿ ðàçëè÷íûõ îãðàíè÷åíèé íà ìàêñèìàëüíûé ðàçìåð âîç-
âðàùåííîãî ìíîæåñòâà �S ïðè èñïîëüçîâàíèè ñëåäóþùèõ ñïîñîáîâ åãî
äîïîëíèòåëüíîé ôèëüòðàöèè:
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 4 39
1) all (áåç ôèëüòðàöèè);
2) = = max (òîëüêî ñòðîêè, ñîâïàâøèå ñ çàïðîñîì q íà ñàìîì ãëóáîêîì óðîâíå
äëÿ äàííîãî S);
3) = = half (ñòðîêè, ñîâïàâøèå íà óðîâíå îò � �K avg äî � �K avg ;
4) >= half (ñòðîêè, ñîâïàâøèå íà óðîâíå, áîëüøåì èëè ðàâíîì K avg ) ,
ãäå K avg — ñðåäíåå çíà÷åíèå óðîâíÿ ñðåäè âîçâðàùåííûõ ñòðîê.
Êàê âèäèì, D M X M YK ( ( ), ( ))� � íåçíà÷èòåëüíî óìåíüøàåòñÿ ïðè óâåëè÷åíèè
L , ÷òî ìîæíî îáúÿñíèòü óâåëè÷åíèåì | |S . Ïîýòîìó êàê è â ïðåäûäóùåì ýêñïå-
ðèìåíòå ìîæíî ñäåëàòü âûâîä î âîçìîæíîñòè ôèêñèðîâàíèÿ L íà íåáîëüøîì
çíà÷åíèè.
Ñïîñîáû ôèëüòðàöèè = = max è = = half èìåþò ïðåèìóùåñòâî ïåðåä äðóãèìè
ñïîñîáàìè, ïîäòâåðæäàÿ ýòèì, ÷òî ñîâïàäåíèå ñòðîê íà áîëåå ãëóáîêèõ óðîâíÿõ
ñâèäåòåëüñòâóåò îá èõ áîëüøåì ñõîäñòâå.
4. ÝÊÑÏÅÐÈÌÅÍÒÛ Ñ ÒÅÊÑÒÎÂÛÌÈ ÊÎËËÅÊÖÈßÌÈ
Ìåòîä, ðàññìîòðåííûé â ðàçä. 3, áûë ïðèìåíåí â çàäà÷å ïîèñêà äóáëèêàòîâ â
òåêñòîâûõ êîëëåêöèÿõ, à òàêæå â çàäà÷å ôèëüòðàöèè ñïàìà â ýëåêòðîííîé ïî÷òå.
Èñïîëüçîâàííûé ïîäõîä ê ðåøåíèþ ýòèõ çàäà÷ îñíîâàí íà ïîèñêå ïðèáëèæåí-
íûõ äóáëèêàòîâ òåêñòîâûõ äàííûõ.
4.1. Çàäà÷à ïîèñêà äóáëèêàòîâ â òåêñòîâûõ êîëëåêöèÿõ
Îïåðàöèÿ ïîèñêà (ïðèáëèæåííûõ) äóáëèêàòîâ òåêñòîâûõ äîêóìåíòîâ òðåáóåò ýô-
ôåêòèâíîãî âûïîëíåíèÿ â ñèñòåìàõ äîêóìåíòîîáîðîòà. Îñîáåííî âîñòðåáîâàííîé
ýòà îïåðàöèÿ ñòàíîâèòñÿ â ïîèñêîâûõ ìàøèíàõ Èíòåðíåò. Äîêóìåíòû, ÿâëÿþùè-
åñÿ ïðèáëèæåííûìè äóáëèêàòàìè îòíîñèòåëüíî îäèí äðóãîãî ÷ðåçâû÷àéíî ðàñ-
ïðîñòðàíåíû â Èíòåðíåòå. ßðêèìè ïðèìåðàìè ÿâëÿþòñÿ ñáîðíèêè FAQ, ñïðàâî÷-
íèêè ïî ÿçûêàì ïðîãðàììèðîâàíèÿ, êîìàíäàì îïåðàöèîííûõ ñèñòåì. Êðîìå
òîãî, íåêîòîðûå òåõíîëîãèè ïðèâëå÷åíèÿ ïîñåòèòåëåé íà ñàéòû ïðåäóñìàòðèâàþò
íàïîëíåíèå «ïîääåëüíûõ» ñòðàíèö ÷àñòÿìè òåêñòîâ ëåãàëüíûõ ñòðàíèö ñ öåëüþ
ïîêàçà ïëàòíîé ðåêëàìû èëè ïåðåíàïðàâëåíèÿ ïîñåòèòåëåé íà äðóãèå ñàéòû.
Îïèñàíèå êîëëåêöèé. Ïîèñê äóáëèêàòîâ îñóùåñòâëÿëñÿ â êîëëåêöèÿõ òåê-
ñòîâ íîâîñòåé Reuters-21578 [17] (21578 òåêñòîâ äëèíîé äî 8316 ñèìâîëîâ) è ó÷åá-
íûõ òåêñòîâ British National Corpus [18] (4054 òåêñòîâ äèíîé äî 2494232 ñèìâîëîâ).
40 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 4
Ðèñ. 3. Çàâèñèìîñòü DK îò êîëè÷åñòâà äåðåâüåâ L äëÿ ðàçìåðîâ ìóëüòèìíîæåñòâà | |S � � 50 (a) è ìóëüòè-
ìíîæåñòâà | |S � � 200 (á)
à á
DK DK
LL
Êîëëåêöèÿ Reuters-21578 ÿâëÿåòñÿ ñòàíäàðòíîé êîëëåêöèé äëÿ èññëåäîâàíèé â
îáëàñòè îáðàáîòêè òåêñòîâîé èíôîðìàöèè. Êîëëåêöèÿ ñîäåðæèò òåêñòû íîâîñòåé
àãåíòñòâà Reuters, ñðåäè êîòîðûõ ìíîãî êàê ïîëíûõ, òàê è ïðèáëèæåííûõ äóáëèêà-
òîâ (óêîðî÷åííûå âåðñèè ðàçâåðíóòûõ íîâîñòåé, äàííûå î êîòèðîâêàõ íà áèðæàõ,
îòëè÷àþùèåñÿ äàòàìè è ÷èñëàìè â òåêñòå, è ò.ï.).
Êîëëåêöèÿ ó÷åáíûõ òåêñòîâ British National Corpus (BNC) — áîëüøàÿ êîëëåê-
öèÿ òåêñòîâ ñîâðåìåííîãî ïèñüìåííîãî è ðàçãîâîðíîãî àíãëèéñêîãî ÿçûêà. Îíà
ïðåäñòàâëÿåò ñîáîé «çîëîòîé ñòàíäàðò» è èñòî÷íèê ñâåäåíèé î «ïðàâèëüíîì» àíã-
ëèéñêîì ÿçûêå (òàê, ñ ïîìîùüþ êîëëåêöèè âû÷èñëÿþòñÿ âåðîÿòíîñòè ïðåôèêñîâ,
îêîí÷àíèé, ñëîâ, èñïîëüçóåìûõ â ðàçíûõ çàäà÷àõ). Òåîðåòè÷åñêè äóáëèêàòîâ
â BNC áûòü íå äîëæíî, ïîñêîëüêó îíè èñêàæàþò ñòàòèñòèêó ïðàâèëüíîãî ÿçûêà.
Ìåòîäèêà ïîèñêà äóáëèêàòîâ. Äëÿ ïîèñêà äóáëèêàòîâ â òåêñòîâûõ êîëëåêöèÿõ
ïðèíèìàåì, ÷òî òàêîâûìè ñ÷èòàþòñÿ òå ñòðîêè, ó êîòîðûõ èìååòñÿ õîòÿ áû îäíî ñîâïà-
äåíèå õåø-âåêòîðîâ äëèíîé K. Íàõîäèì äóáëèêàòû, ÷èñëî êîòîðûõ çàâèñèò îò äëèíû
îáðåçêè òåêñòà n � 100, 150, 250, 500, 1000, 2000 ñèìâîëàõ, à òàêæå êîëè÷åñòâî äóáëèêà-
òîâ äëÿ òåêñòîâ áåç îáðåçêè (âûðàâíèâàíèå ïî ìàêñèìàëüíîé äëèíå, óñëîâíî îáîçíà÷àå-
ìîå n � 0). Èñïîëüçóåì ñëåäóþùèå ïàðàìåòðû ñõåìû LSH: êîëè÷åñòâî äåðåâüåâ L � 1, 5;
ðàçìåðíîñòè õåø-âåêòîðîâ K � 1, 2, 5, 10, 25, 50, 100, 150, 200.
Èñïîëüçîâàëàñü ïðåäâàðèòåëüíàÿ ôèëüòðàöèÿ òåêñòîâ, îñòàâëÿþùàÿ òîëüêî
ñèìâîëû è öèôðû (C-ôóíêöèÿ isalnum()). Çàãîëîâêè íîâîñòíûõ òåêñòîâ âêëþ÷àëèñü
â òåêñò, à ïðîïèñíûå áóêâû çàìåíÿëèñü ñòðî÷íûìè. Êîðîòêèå òåêñòû, äëèíà êîòî-
ðûõ ìåíüøå äëèíû îáðåçêè n , äîïîëíÿëèñü äî óêàçàííîé äëèíû îäèíàêîâûì ñïå-
öèàëüíûì ñèìâîëîì â êîíöå òåêñòà.
Îïðåäåëåíèå êîëè÷åñòâà íàéäåííûõ äóáëèêàòîâ â êîëëåêöèÿõ. Íàéäåí-
íîå êîëè÷åñòâî ïðèáëèæåííûõ äóáëèêàòîâ â êîëëåêöèÿõ Reuters-21578 è BNC â çà-
âèñèìîñòè îò çíà÷åíèé K è n ïðèâåäåíî ñîîòâåòñòâåííî â òàáë. 2 è 3 äëÿ L � 1 è
L � 5. Èñïîëüçîâàëèñü ñèìâîëû Ñ-ôóíêöèè isalnum().
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 4 41
Ò à á ë è ö à 2
K
Êîëè÷åñòâî íàéäåííûõ ïðèáëèæåííûõ äóáëèêàòîâ
L � 1
n �100 n � 150 n � 250 n � 500 n �750 n �1000 n �2000 n �0
1 21347 21334 21281 21224 21206 21213 21275 21458
2 20310 20183 19761 19312 19259 19271 19898 21442
5 8715 7780 5670 5450 7507 10244 15595 20725
10 409 379 806 2124 3273 4721 11109 19199
25 371 350 329 553 1504 1875 4280 17533
50 371 349 325 376 990 1444 3409 15227
100 370 346 322 305 268 271 584 4960
150 370 346 322 305 267 262 479 4823
200 369 346 322 305 267 261 264 2748
K L � 5
1 20709 20637 19326 21207 20860 21015 21034 21575
2 19531 19185 19439 19676 19094 20157 20384 21453
5 15513 14532 11858 9593 10393 12436 16536 20658
10 973 1251 2418 4552 6442 8407 14815 20664
25 689 629 615 1832 3168 3769 7238 17401
50 674 600 523 672 1459 2245 4266 14372
100 666 595 513 487 462 505 1592 6497
150 662 592 513 474 437 447 1253 5625
200 661 591 511 467 429 422 591 3499
×èñëî ïðèáëèæåííûõ äóáëèêàòîâ åñòåñòâåííî óìåíüøàåòñÿ ïðè óâåëè÷åíèè K , ñòà-
áèëèçèðóÿñü ïðè áîëüøèõ K íà çíà÷åíèÿõ, ïðèáëèçèòåëüíî ñîîòâåòñòâóþùèõ êîëè÷åñòâó
äóáëèêàòîâ, íàéäåííûõ ìåòîäîì, ðàññìîòðåííûì â ðàáîòå [19] (320 äóáëèêàòîâ). Áîëüøîå
÷èñëî ïðèáëèæåííûõ äóáëèêàòîâ â ñëó÷àå, êîãäà îáðåçêè ïî ôèêñèðîâàííîé äëèíå íå èñ-
ïîëüçóþòñÿ (è èõ óâåëè÷åíèå äëÿ ýêñïåðèìåíòà ñ ñèìâîëàìè isalnum() äëÿ n � 2000), îáú-
ÿñíÿåòñÿ áîëüøèì ñõîäñòâîì ìíîãèõ ñòðîê, òàê êàê ê íèì äîáàâëÿëèñü îäèíàêîâûå ñèìâî-
ëû äëÿ âûðàâíèâàíèÿ äëèíû. Ïðè óâåëè÷åíèè L êîëè÷åñòâî äóáëèêàòîâ òàêæå óâåëè÷èâà-
åòñÿ, ïîñêîëüêó óâåëè÷èâàåòñÿ âåðîÿòíîñòü ñîâïàäåíèÿ K ýëåìåíòîâ õîòÿ áû ó îäíîãî
äåðåâà. Ïðè âèçóàëüíîé ïðîâåðêå, îäíàêî, íåêîòîðûå äóáëèêàòû îêàçàëèñü òî÷íûìè.
Óìåíüøåíèå êîëè÷åñòâà äóáëèêàòîâ ïðè óâåëè÷åíèè äëèíû îáðåçêè äëÿ K � 10 ïðè âèçó-
àëüíîé ïðîâåðêå âûçâàíî ìåëêèìè îïå÷àòêàìè â òåêñòàõ. Ïðè ìåíüøèõ çíà÷åíèÿõ K ýòè
îïå÷àòêè ìîãóò íå âûçûâàòü íåñîâïàäåíèé õåø-âåêòîðîâ.
42 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 4
Ðèñ. 4. Çàâèñèìîñòü òî÷íîñòè p îò ïîëíîòû r äëÿ çíà÷åíèé sim � 0 95. (à) è sim � 0 99. (á) ïðè L � 5
à á
r r
p p
Ò à á ë è ö à 3
K
Êîëè÷åñòâî íàéäåííûõ ïðèáëèæåííûõ äóáëèêàòîâ
L � 1
n �100 n �150 n �250 n �500 n �750 n �1000 n �2000 n �0
1 3943 3933 3915 3902 3888 3857 3832 4027
2 3545 3470 3346 3203 3044 2941 2619 4027
5 895 668 297 84 39 31 15 3523
10 10 9 9 8 8 9 9 3447
25 9 9 9 8 8 8 7 3403
50 9 9 9 8 8 8 7 2421
100 9 9 9 8 8 8 7 1263
150 9 9 9 8 8 8 7 1263
200 9 9 9 8 8 8 7 246
K L � 5
1 3587 3867 3782 3680 3543 3706 3645 4052
2 3618 3716 3613 3374 3503 3489 3349 4037
5 2187 1855 1020 378 168 81 37 4008
10 12 10 9 8 8 10 18 3997
25 9 9 9 8 8 8 9 3493
50 9 9 9 8 8 8 7 2430
100 9 9 9 8 8 8 7 1738
150 9 9 9 8 8 8 7 –
200 9 9 9 8 8 8 7 –
Âðåìÿ ïîèñêà âñåõ äóáëèêàòîâ ðàâíî âðåìåíè îáõîäà âñåõ ëèñòüåâ â LSH-äåðå-
âå è íå ïðåâûøàåò 0.2 ñåê íà ñòàíäàðòíîì êîìïüþòåðå AMD Athlon XP 2600 ñ
1.5 Ãá ïàìÿòè.
Ñðàâíèòåëüíûå ðåçóëüòàòû ïîèñêà äóáëèêàòîâ. Ðåçóëüòàòû ïîèñêà äóá-
ëèêàòîâ ñðàâíèâàëèñü ñ ìåòîäîì äåòåðìèíèðîâàííîãî âëîæåíèÿ, îïèñàííûì â
[21]. Çà «çîëîòîé ñòàíäàðò» áûëè âûáðàíû ïàðû äóáëèêàòîâ êàê òàêîé, íà êîòî-
ðîé çíà÷åíèå ôóíêöèè PERL String::Similarity (îñíîâàííîé íà ðàññòîÿíèè ðåäàê-
òèðîâàíèÿ) íå ìåíüøå 0.85 (òàêîé æå ïîäõîä ïðèìåíÿëñÿ äëÿ ñîçäàíèÿ êîëëåê-
öèè äóáëèêàòîâ â [20]) .
Îáîçíà÷èì Tsim ìíîæåñòâî òåêñòîâ ñî çíà÷åíèåì ôóíêöèè String::Similarity,
á�ëüøèì èëè ðàâíûì sim. Ïðèíèìàÿ ïîî÷åðåäíî çà «çîëîòîé ñòàíäàðò» ìíîæåñòâà
T T0 95 0 99. ., , ìîæíî îöåíèòü êà÷åñòâî ðàáîòû íàøåãî ìåòîäà ñ ïîìîùüþ ãðàôèêîâ
òî÷íîñòü–ïîëíîòà ïóòåì èçìåíåíèÿ çíà÷åíèÿ K (èñïîëüçîâàëèñü çíà÷åíèÿ K � 5,
10, 25, 50, 100, 150, 200). Êàê âèäíî èç ðèñ. 4, ïðè óâåëè÷åíèè ïîðîãà Tsim íà çíà÷å-
íèå ôóíêöèè String::Similarity ïîëíîòà óâåëè÷èâàåòñÿ, ò.å. á�ëüøàÿ äîëÿ «ïðàâèëü-
íûõ» äóáëèêàòîâ ïîïàäàåò â ìóëüòèìíîæåñòâî S , äîñòèãàÿ åäèíèöû ïðè sim � 1
(ñ÷èòàþòñÿ òîëüêî ïîëíûå äóáëèêàòû). Óìåíüøåíèå òî÷íîñòè ïðè óâåëè÷åíèè äëè-
íû îáðåçêè n îáúÿñíÿåòñÿ áîëåå ÷àñòûì «ñðàáàòûâàíèåì» ìåòîäà íà áîëüøåì êîëè-
÷åñòâå ñïåöèàëüíûõ ñèìâîëîâ, ñ ïîìîùüþ êîòîðûõ âûðàâíèâàëàñü äëèíà òåêñòîâ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 4 43
Ðèñ. 6. Çíà÷åíèÿ F1 max äëÿ n � 250 (à) è n � 500 (á)
à á
F F
sim sim
Ðèñ. 5. Çàâèñèìîñòü òî÷íîñòè p îò ïîëíîòû r äëÿ ìåòîäà BY ïðè sim � 0 95. (à) è sim � 0 99. (á)
à á
p p
rr
Àíàëîãè÷íûå ãðàôèêè áûëè ïîñòðîåíû íà ðèñ. 5 äëÿ ìåòîäà äåòåðìèíèðîâàí-
íîãî âëîæåíèÿ (BY), îïèñàííîãî â ðàáîòå [21], äëÿ äëèíû îáðåçîê n � 100, 150, 250,
500, 750 (äëÿ á�ëüøèõ çíà÷åíèé n íå óäàëîñü ïîëó÷èòü ðåçóëüòàòîâ çà ïðèåìëåìîå
âðåìÿ). Äëÿ ïîñòðîåíèÿ ãðàôèêîâ èçìåíÿëñÿ ïîðîã íà ðàññòîÿíèÿ Õåììèíãà ìåæäó
ïîëó÷åííûìè âåêòîðàìè, îïðåäåëÿþùèé, ìîæíî ëè ñ÷èòàòü åãî äóáëèêàòîì. Ïðî-
âåðÿëèñü òîëüêî òåêñòû, ãäå ðàññòîÿíèå Õåììèíãà íå ïðåâûøàëî 15% ìàêñèìàëüíî
âîçìîæíîãî äëÿ äàííîé äëèíû n.
Äëÿ ñðàâíåíèÿ ïàð çíà÷åíèé òî÷íîñòü–ïîëíîòà èñïîëüçîâàëàñü èíòåãðàëüíàÿ
îöåíêà F-measure ñ � � 1, îïðåäåëÿåìàÿ êàê F r r� � �� � �( ) / ( )1 p p [22], ãäå r — ïî-
ëíîòà, p — òî÷íîñòü. Äëÿ êàæäîé êðèâîé, èçîáðàæåííîé íà ðèñ. 4, 5, áûëî ïîäñ÷è-
òàíî ìàêñèìàëüíîå çíà÷åíèå F1max , äîñòèãàåìîå íà òî÷êàõ ýòîé êðèâîé. Ïîëó÷åí-
íûå çíà÷åíèÿ äëÿ n � 250 è n � 500 èçîáðàæåíû íà ðèñ. 6. Òî÷êè (êðåñòèêè), îáîçíà-
÷åííûå â ëåãåíäå BY, ñîîòâåòñòâóþò àëãîðèòìó èç [21], ïëþñèêè — àëãîðèòìó
ïîèñêà ñ ïîìîùüþ LSÍ-ëåñà.
Ðåçóëüòàòû ïîêàçûâàþò îòñóòñòâèå ñóùåñòâåííûõ ðàçëè÷èé ìåæäó äâóìÿ
ñðàâíèâàåìûìè ìåòîäàìè îòíîñèòåëüíî «çîëîòîãî ñòàíäàðòà», îäíàêî âðåìÿ ðåøå-
íèÿ çàäà÷è ñóùåñòâåííî îòëè÷àåòñÿ. Ïîðÿäîê âðåìåíè ïîèñêà äóáëèêàòîâ íà âñåé
êîëëåêöèè ñ ó÷åòîì ïîñòðîåíèÿ äåðåâüåâ â ìåòîäå, îñíîâàííîì íà ïðèìåíåíèè
LSH-ëåñà, ñîñòàâëÿåò ìèíóòû, òîãäà êàê â ñëó÷àå ïðèìåíåíèÿ äåòåðìèíèðîâàííîãî
ìåòîäà BY èç [21] — îò ÷àñîâ äî äíåé.
Èññëåäîâàëîñü òàêæå êà÷åñòâî ïîèñêà äóáëèêàòîâ íà ñòàíäàðòíîé áàçå «Äóáëè
Web-ñòðàíèö êîëëåêöèè ÐÎÌÈÏ» [20] (ïðåäîñòàâëåíà êîìïàíèåé «ßíäåêñ»), ñî-
äåðæàùåé ñïèñîê áîëåå 10 ìëí. ïàð âåá-ñòðàíèö, ñõîäñòâî ìåæäó êîòîðûìè ïî çíà-
÷åíèþ ôóíêöèè PERL String::Similarity íå ìåíåå 0.85. Èñïîëüçîâàëàñü ìîäèôèêà-
öèÿ ìåòîäà ïîèñêà äóáëèêàòîâ, îïèñàííàÿ âûøå (ïîèñê äóáëèêàòîâ ïðîèçâîäèëñÿ
ëèøü ñðåäè äîêóìåíòîâ, äëèíà êîòîðûõ ïðèáëèçèòåëüíî ðàâíà äëèíå çàïðîñà). Ïî-
ëó÷åíû çíà÷åíèÿ îöåíêè F-measure äî 0.88 â çàâèñèìîñòè îò ïîðîãà íà çíà÷åíèå
ôóíêöèè PERL String::Similarity è ïàðàìåòðîâ K L, .
4.2. Çàäà÷à îöåíêè êîëè÷åñòâà ñïàìà â êîëëåêöèÿõ ýëåêòðîííûõ ïèñåì
Îáíàðóæåíèå ïî÷òîâîãî ñïàìà ÿâëÿåòñÿ àêòóàëüíîé çàäà÷åé, ïîñêîëüêó êîëè÷åñòâî
ñïàìà ñðåäè âñåé ïî÷òû ó ñðåäíåãî ïîëüçîâàòåëÿ â 2005 ãîäó óæå äîñòèãàëî 80–85%
[23] è ïðîäîëæàåò óâåëè÷èâàòüñÿ. Ñïàì îáíàðóæèâàþò ðàçëè÷íûìè ñïîñîáàìè — â
îñíîâíîì ýòî ïðîâåðêè íà ñïåöèôè÷åñêèå îñîáåííîñòè ñïàì-ïèñåì, òàêèå êàê íàõîæ-
äåíèå àäðåñà àäðåñàíòà â ÷åðíîì ñïèñêå, ïðèìåíåíèå ðàçìåòêè HTML â ïèñüìå, ïî-
äîçðèòåëüíûå âëîæåíèÿ. Èñïîëüçóþò òàêæå áàéåñîâñêóþ êëàññèôèêàöèþ [24].
Îäíîé èç ðàñïðîñòðàíåííûõ ñïàì-òåõíîëîãèé, ïîçâîëÿþùèõ ïðåîäîëåòü ïðî-
ñòåéøèå ÷àñòîòíûå ôèëüòðû, ÿâëÿåòñÿ âíåñåíèå èçìåíåíèé â òåêñò ïèñüìà (íàïðè-
ìåð, ñïåöèôè÷åñêîå íàïèñàíèå ñëîâ, êîòîðûå ïåðåñòàþò áûòü òî÷íûìè êîïèÿìè
äðóã äðóãà è èñêàæàþò êàðòèíó âåðîÿòíîñòåé ñëîâ èëè ïðåïÿòñòâóþò ïðåäâàðèòåëü-
íîé îáðàáîòêå ïèñåì ôèëüòðàìè [25]). Äëÿ áîðüáû ñ ïîäîáíûìè òåõíîëîãèÿìè íå-
êîòîðûå èññëåäîâàòåëè ïðåäëàãàþò îáíàðóæåíèå ñïàìà ñ èñïîëüçîâàíèåì ñðàâíå-
íèÿ ïèñåì ñ ðàíåå ñîõðàíåííûìè [26]. Ìû èññëåäîâàëè ðåàëèçàöèþ äàííîé èäåè íà
îñíîâå ðàçðàáîòàííûõ ìåòîäîâ ïðÿìîãî ñðàâíåíèÿ òåêñòîâûõ ñòðîê-ïèñåì. Òàêèì
îáðàçîì, ìû îöåíèëè, êàêîå êîëè÷åñòâî ñïàìà ìîæåò áûòü îáíàðóæåíî âñåãî ëèøü
ñ ïîìîùüþ ñðàâíåíèÿ ñ ðàíåå ïîñòóïèâøèìè ñïàì-ïèñüìàìè áåç ïðèìåíåíèÿ
ñïåöèôè÷åñêèõ çíàíèé è ïîäðîáíîãî àíàëèçà ñïàì-òåõíîëîãèé.
Îïèñàíèå èñïîëüçîâàííûõ êîëëåêöèé. Áûëà èñïîëüçîâàíà òåñòîâàÿ áàçà
TREC 2006 Spam Track [27], øèðîêî ïðèìåíÿåìàÿ ðàçðàáîò÷èêàìè ñèñòåì îáíàðó-
æåíèÿ ñïàìà äëÿ òåñòèðîâàíèÿ ñâîèõ ïðîäóêòîâ. Îíà ñîäåðæèò ïî÷òîâûå ñîîáùå-
íèÿ, ðàçìå÷åííûå ýêñïåðòàìè êàê ñïàì è íå ñïàì. Àíãëîÿçû÷íàÿ ÷àñòü áàçû TREC
2006 Spam Track ñîäåðæèò | |P � 37822 ðàçìå÷åííûõ ðåàëüíûõ ïî÷òîâûõ ñîîáùåíèé
îáúåìîì 189 Ìá, èç êîòîðûõ 24912 (66%) — ñïàì.
44 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 4
Ñõåìà ýêñïåðèìåíòîâ è îöåíêà ýôôåêòèâíîñòè. Êîëëåêöèè â TREC è ïðèíÿ-
òûé ñïîñîá îöåíêè ýôôåêòèâíîñòè ôèëüòðîâ ïîñòðîåíû ñ ó÷åòîì ñïîñîáà ðåàëüíîãî èñ-
ïîëüçîâàíèÿ ñïàì-ôèëüòðîâ êîíå÷íûìè ïîëüçîâàòåëÿìè. Çàäà÷à òåñòèðóåìûõ ôèëüò-
ðîâ — êëàññèôèöèðîâàòü ïîäàâàåìûå â õðîíîëîãè÷åñêîì ïîðÿäêå ñîîáùåíèÿ è çà-
òåì äîîáó÷èòüñÿ ïîñëå ïîëó÷åíèÿ ïðàâèëüíîãî êëàññà äëÿ ýòîãî ñîîáùåíèÿ îò
ýêñïåðòà. Ýòîò ïðîöåññ ñîîòâåòñòâóåò îáû÷íîìó ïîðÿäêó äåéñòâèé ïîëüçîâàòåëÿ,
êîãäà îí ïîñëåäîâàòåëüíî âûáèðàåò èç âõîäÿùèõ ñîîáùåíèé ñïàì, ïîçâîëÿÿ, òàêèì
îáðàçîì, áîëåå òî÷íî íàñòðîèòü ôèëüòð.
Ïî óñëîâèÿì TREC êàæäîìó ïèñüìó äîëæåí áûòü ïðèñâîåí ïàðàìåòð — ñòå-
ïåíü «ñïàìíîñòè» ïèñüìà (score), ïî êîòîðîìó îíî êëàññèôèöèðóåòñÿ: ñîîáùåíèÿ,
ïîëó÷èâøèå score áîëüøå îïðåäåëåííîãî ïîðîãà, ñ÷èòàþòñÿ ñïàìîì, îñòàëüíûå —
îáû÷íûìè ïèñüìàìè. Îöåíêà êà÷åñòâà ðàáîòû ôèëüòðà ïðîâîäèòñÿ ïî äâóì îñíîâ-
íûì ïàðàìåòðàì — ïðîöåíòó íåïðàâèëüíî êëàññèôèöèðîâàííûõ ñïàì-ñîîáùåíèé
sm% (false positives) è ïðîöåíòó íåïðàâèëüíî êëàññèôèöèðîâàííûõ íåñïàì-ñîîáùå-
íèé hm% (false negatives). Èçìåíåíèåì ïîðîãà íà çíà÷åíèå score ìîæíî ïîñòðîèòü
ROC-êðèâûå (çàâèñèìîñòü sm% îò hm%), ïî êîòîðûì â TREC ñðàâíèâàþòñÿ ðàçëè÷-
íûå àëãîðèòìû.
Ýêñïåðèìåíòû è ïðèñâîåíèå score. Ïðåäâàðèòåëüíûé ôèëüòð îñòàâëÿë â
ïèñüìàõ îäíè ëèøü ñèìâîëû àëôàâèòà (Ñ-ôóíêöèÿ isalpha()) è îáðåçàë ñîîáùåíèå
ïî ðàçìåðó n � 1000. Ïîäàâàåìûå â õðîíîëîãè÷åñêîì ïîðÿäêå ñîîáùåíèÿ èç êîëëåê-
öèé ñëóæèëè çàïðîñàìè äëÿ ïðîöåäóðû ïîèñêà ïðèáëèæåííîãî áëèæàéøåãî ñîñåäà
ñ ïîìîùüþ LSH-ëåñà. Çíà÷åíèå L èçìåíÿëîñü îò 1 äî 200. Çíà÷åíèå K ôèêñèðîâà-
ëîñü ïî ôîðìóëå (9) LSH-ñõåìû äëÿ çàäàííûõ p P2 , (ñì. ðàçä. 2).
Íà îñíîâàíèè ýêñïåðèìåíòîâ, ðàññìîòðåííûõ â ðàçä. 3, âûáðàíû äâà ñïîñîáà
ïðèñâîåíèÿ score ïèñüìàì ïî óðîâíþ â LSH-ëåñå, êîòîðîìó ïðèíàäëåæàò ïðèáëè-
æåííûå áëèæàéøèå ñîñåäè ê âõîäíûì ïèñüìàì: ïî ìàêñèìàëüíîìó óðîâíþ
k Kmax � è ïî ñðåäíåìó óðîâíþ kavg .
Åñëè ñîîáùåíèå â äåéñòâèòåëüíîñòè èìåëî â êîëëåêöèè ýêñïåðòíóþ ìåòêó
«ñïàì», òî îíî äîáàâëÿëîñü â ìíîæåñòâî Ð è íà êëàññèôèêàöèþ ïîäàâàëîñü
ñëåäóþùåå ñîîáùåíèå.
Ðåçóëüòàòû. Íà ðèñ. 7 ïðèâåäå-
íû ROC-êðèâûå äëÿ ñïîñîáà íàçíà÷å-
íèÿ score ïî ìàêñèìàëüíîìó óðîâíþ
(ñïîñîá ïî ñðåäíåìó óðîâíþ äàåò
ïîäîáíûå ðåçóëüòàòû). Êàê âèäèì,
ïðè óðîâíå hm% %� �5 10 óñïåøíî
îáíàðóæèâàåòñÿ ïðèáëèçèòåëüíî 80%
ñïàìà äëÿ Spam Track 2006.
Ýêñïåðèìåíòàëüíî óñòàíîâëåíî,
÷òî ðåàëèçîâàâ èäåþ îáíàðóæåíèÿ ñïà-
ìà ïî ïðèáëèæåííûì äóáëèêàòàì,
ìîæíî îòôèëüòðîâàòü çíà÷èòåëüíóþ
åãî ÷àñòü, ÷òî ïîçâîëÿåò ñóäèòü î ïðè-
ìåíèìîñòè äàííîãî ïîäõîäà â áîëüøèõ
ïî÷òîâûõ ñåðâåðàõ â êà÷åñòâå ñîñòàâ-
íîé òåõíîëîãèè (ìîäóëÿ) â áîëåå ñëîæ-
íûõ ñèñòåìàõ. ×åì áîëüøå öåíòðàëèçî-
âàí ïî÷òîâûé ñåðâèñ è ÷åì áîëüøåå ó
íåãî ÷èñëî ïîëüçîâàòåëåé, òåì áîëü-
øèé ïðîöåíò îòôèëüòðîâàííîãî ñïàìà
ìîæíî ïîëó÷èòü.
Èç ROC-êðèâûõ íà ðèñ. 7 âèäíî, ÷òî ïðè L � 1çíà÷åíèÿ hm% ÷àñòî ïîëó÷àþòñÿ
ìåíüøå, ÷åì ïðè L
1. Ýòî îáúÿñíÿåòñÿ âûñîêîé ñòåïåíüþ ñõîäñòâà ÷àñòè ëåãàëü-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 4 45
Ðèñ. 7. Çàâèñèìîñòü çíà÷åíèÿ sm% îò hm% äëÿ
êîëëåêöèè Spam Track 2006 äëÿ ñïîñîáà íàçíà÷åíèÿ
score ïî ìàêñèìàëüíîìó óðîâíþ. Äëèíà n � 1000
sm%
hm%
íûõ ïèñåì ñî ñïàìîì, íàïðèìåð ââèäó èñïîëüçîâàíèÿ html-ôîðìàòà, êîòîðûé
îñòàâëÿëñÿ â ïèñüìå, à íå óáèðàëñÿ è/èëè íå àíàëèçèðîâàëñÿ åãî êîä, êàê ýòî ïðèíÿ-
òî â ðåàëüíûõ ñèñòåìàõ îáíàðóæåíèÿ ñïàìà.
5. ÇÀÊËÞ×ÅÍÈÅ
Ïðîâåäåííûå ýêñïåðèìåíòû ïîäòâåðäèëè ýôôåêòèâíîñòü ìåòîäà âëîæåíèÿ ðàñ-
ñòîÿíèÿ ðåäàêòèðîâàíèÿ â âåêòîðíîå ïðîñòðàíñòâî, à òàêæå îñíîâàííîãî íà íåì
ðàíäîìèçèðîâàííîãî ìåòîäà, êàê ìåòîäîâ íàõîæäåíèÿ ïðèáëèæåííî áëèæàéøèõ
ñòðîê [6]. Ïîêàçàíà âîçìîæíîñòü ïðèìåíåíèÿ ðàíäîìèçèðîâàííîãî ìåòîäà â ðå-
àëüíûõ ïðàêòè÷åñêèõ çàäà÷àõ ïîèñêà äóáëèêàòîâ è îáíàðóæåíèÿ ñïàìà. Ó÷èòû-
âàÿ ïðè ðåøåíèè ýòèõ çàäà÷ íàìåðåííîå èãíîðèðîâàíèå èíôîðìàöèè î ñïåöèôè-
êå ïðåäìåòíîé îáëàñòè, êîòîðàÿ îáÿçàòåëüíî äîëæíà èñïîëüçîâàòüñÿ ïðè ðåøå-
íèè ðåàëüíûõ çàäà÷ íà ïðàêòèêå, ïðåäëîæåííûé ìåòîä ïîêàçàë õîðîøèå
ðåçóëüòàòû â çàäà÷å îöåíêè êîëè÷åñòâà ïî÷òîâîãî ñïàìà è ìîæåò ïðèìåíÿòüñÿ
êàê ñîñòàâíàÿ ÷àñòü â ñèñòåìàõ îáíàðóæåíèÿ ñïàìà.
Ìû ïîëàãàåì, ÷òî ñèñòåìû, îñíîâàííûå íà îáíàðóæåíèè ñïàìà êàê ïðèáëè-
æåííûõ êîïèé, áóäóò îñîáåííî ýôôåêòèâíû â áîëüøèõ ïî÷òîâûõ ñåðâèñàõ òèïà
Gmail. Ïîñêîëüêó ñïàì âñåãäà íàïðàâëÿåòñÿ áîëüøîìó ÷èñëó ïîëó÷àòåëåé, ñëåäóåò
îæèäàòü, ÷òî íà ïî÷òîâîì ñåðâèñå îáíàðóæèòü åãî íàìíîãî ëåã÷å, ÷åì â ðàìêàõ ïî-
÷òîâîãî ÿùèêà èíäèâèäóàëüíîãî ïîëüçîâàòåëÿ, ãäå ïîõîæèé ñïàì ïðèõîäèò â ãîðàç-
äî áîëåå ñêðîìíûõ ìàñøòàáàõ. Äëÿ èíäèâèäóàëüíûõ ïîëüçîâàòåëåé ïîäîáíûé ïîä-
õîä ìîæíî ïðèìåíÿòü, ïåðåéäÿ ê êîîïåðàòèâíîìó îáíàðóæåíèþ ñïàìà.  êà÷åñòâå
ïðèìåðà ìîæíî ïðèâåñòè ðàñïðåäåëåííóþ ñèñòåìó Vipul îáíàðóæåíèÿ ñïàìà, êîòî-
ðàÿ èñïîëüçóåò ñêåò÷è ñîîáùåíèé, îòìå÷åííûõ êàê ñïàì ó÷àñòíèêàìè ñèñòåìû. Â
êà÷åñòâå òàêèõ ñêåò÷åé ìîæíî ðàññìîòðåòü ïðåäëàãàåìûå íàìè õåø-âåêòîðû.
 äàëüíåéøåì ïðåäïîëàãàåòñÿ ïðèìåíèòü ïîäõîä ê ïîèñêó ïðèáëèæåííûõ
äóáëèêàòîâ íà îñíîâå ïðåäëîæåííîãî ìåòîäà âëîæåíèÿ ðàññòîÿíèÿ ðåäàêòèðîâàíèÿ
â äðóãèõ ïðàêòè÷åñêèõ çàäà÷àõ, òàêèõ êàê ïîèñê ãåíîâ èëè àíàëèç ëîãîâ â
êîìïüþòåðíûõ ñèñòåìàõ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. B r i n S . , D a v i s J . , G a r c i a - M o l i n a H . Copy detection mechanisms for digital documents //
Proc. SIGMOD. — 1995. — P. 398–409
2. G u s f i e l d D . Algorithms on strings trees and sequences. — Cambridge: Cambridge Univeristy Press,
1997. — 532 p.
3. Ë å â å í ø ò å é í  . È . Äâîè÷íûå êîäû ñ èñïðàâëåíèåì âûïàäåíèé, âñòàâîê è çàìåùåíèé ñèìâîëîâ
// Äîêë. ÀÍ ÑÑÑÐ. — 1965. — 163, âûï. 4. — Ñ. 845–848.
4.  è í ö þ ê Ò . Ê . Ðàñïîçíàâàíèå ñëîâ óñòíîé ðå÷è ìåòîäàìè äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ //
Êèáåðíåòèêà. — 1968. — ¹ 1. — C. 81–88.
5. I n d y k P . Open problems // Workshop on discrete metric spaces and their algorithmic applications / Ed.
by Jiri Matousek. — Haifa, Israel, 2002.
6. Ñ î ê î ë î â À . Ì . Âåêòîðíûå ïðåäñòàâëåíèÿ äëÿ ýôôåêòèâíîãî ñðàâíåíèÿ è ïîèñêà ïîõîæèõ ñòðîê
// Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2007. — ¹ 4. — C. 18–38.
7. I n d y k P . , M o t w a n i R . Approximate nearest neighbors: towards removing the curse of
dimensionality // Proc. of 30th STOC. — 1998. — P. 604–613.
8. L o c a l i t y - s e n s i t i v e hashing scheme based on p-stable distributions / M. Datar, N. Immorlica,
P. Indyk, V. Mirrokni // 20-th Symposium on Computational Geometry, 2004. — P. 253–262.
9. U k k o n e n E . Approximate string-matching with q-grams and maximal matches // Theor. Comput. Sci.
— 1992 — 92, N 3. — P. 191–211.
10. S o k o l o v A . Nearest string by neural-like encoding // Proc. XI-th Conf. Knowledge-Dialogue-Solution.
— Varna, Bulgaria, 2006 — P. 101–106.
11. B a w a M . , C o n d i e T . , G a n e s a n P . LSH forest: self-tuning indexes for similarity search // Proc.
of the 14th Conference on WWW. — New York: ACM Press, 2005. — P. 651–660.
46 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 4
12. A z e n k o t S . , C h e n T . - Y . , C o r m o d e G . An evaluation of the edit-distance-with-moves metric
for comparing genetic sequences // DIMACS Technical Report 2005-39. — 2005.
13. B a e z a - Y a t e s R . , N e t o R . Modern Information Retrieval. — ACM Press Series/Addison Wesley,
— New York, 1999 — 544 p.
14. S p i n k A . , B a t e m a n J . , J a n s e n B . J . Searching the Web: Survey of EXCITE users // Internet
Research: Electronic Networking Applications and Policy. — 1999. — 9, N 4. — P. 117–128.
15. H a w k i n g D . , V o o r h e e s E . , C r a s w e l l N . , B a i l e y P . Overview of the TREC8 Web Track
// 8th Text REtrieval Conference. — Gaithersburg, 1999.
16. F a g i n R . , K u m a r R . , S i v a k u m a r D . Comparing top k lists // SIAM J. on Discrete Mathematics,
2003. — P. 134–160.
17. R e u t e r s - 21578. — http://www.daviddlewis.com/resources/testcollections/reuters21578/
18. T h e B r i t i s h National Corpus. — http://www.natcorp.ox.ac.uk/
19. S a n d e r s o n M . Duplicate detection in the Reuters collection // Technical Report (TR-1997-5). —
Department of Computing Science at the University of Glasgow. — Glasgow, UK, 1997.
20. Í à á î ð û äàííûõ êîíêóðñà «Èíòåðíåò-Ìàòåìàòèêà». — ßíäåêñ. — http://company.yandex.ru/grant/
datasets_description.xml. 2007
21. A p p r o x i m a t i n g Edit Distance Efficiently / Z. Bar-Yossef, T. S. Jayram, R. Krauthgamer, R. Kumar //
Proc. of the 45th IEEE Symposium on Foundations of Computer Science // IEEE, 2004 — P. 550–559.
22. V a n R i j s b e r g e n C . J . Information Retireval. — London: Butterworths, 1979 — 208 p.
23. M e s s a g i n g anti-abuse working group. “Email Metrics Program: The Network Operators’ Perspective”.
Report N 1 — 4th Quarter. — 2005.
24. G r a h a m P . Plan for Spam. — http://www.paulgraham.com/stopspam.html, 2002.
25. G r a h a m - C u m m i n g J . The Spammers’ Compendium // Spam Conference at MIT, 2003. —
http://www.jgc.org/tsc.html
26. K o l c z A . , C h o w d h u r y A . , A l s p e c t o r J . The impact of feature selection on signature-driven
spam detection // Proc. of the 1st Conf. on Email and Anti-Spam, 2004. — http://www.ceas.cc/
papers-2004/147.pdf
27. C o r m a c k G . V . TREC 2006 Spam Track Overview // Proc. of the 15th Text REtrieval Conf. — NIST.
— Gaithersburg, MD, 2006.
Ïîñòóïèëà 09.08.2007
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 4 47
|