Поиск сходства Интернет-документов с помощью частых замкнутых множеств признаков. - часть 5

нарезка шинглов с заданными параметрами;

хэширование шинглов;

составление образа документов путем выбора подмножества (хэш-кодов) шинглов с помощью методов «n минимальных элементов в перестановке» и «минимальные элементы n n перестановках»;

cоставление по результатам методов 4-5 инвертированной таблицы «список идентификаторов документов—шингл» — подготовка данных к формату программ вычисления замкнутых множеств;

вычисление частых замкнутых множеств с заданным порогом общего числа документов, в которое входит данное множество шинглов: программа MyFim (реализующая алгоритм FPmax*);

сравнение со списком дубликатов РОМИП – программа Comparator.

В качестве экспериментального материала нами использовалась URL-коллекция РОМИП, состоящая из 52 файлов общего размера 4,04 Гб. Для проведения экспериментов коллекция разбивалась на несколько частей, включающих от трех до двадцати четырех файлов (приблизительно от 5% до 50% от размера всей коллекции).

В экспериментах использовались следующие пПараметры шинглирования: число слов в шингле 10 и 20, отступ между началом соседних шинглов 1. Данное значение отступа означает, что начальное множество шинглов включало все возможные последовательности цепочек слов.

Эксперименты проводились на персональном компьютере P-IV HT с тактовой частотой 3.0 ГГц, оперативной памятью объемом в 1024 Мб и операционной системой Windows XP Professional. Результаты экспериментов и время, затраченное на их проведение, частично приводятся в следующих таблицах и рисунках.

(1) Результаты работы метода “

минимальных элементов в перестановке”

FPmax		All Pairs of Duplicates		Unique pairs of duplicates		Common pairs
Input	Threshold	ROMIP	Test	ROMIP	Test
b_1_20_s_100_n1-6.txt	100	33267	7829	28897	3459	4370
b_1_20_s_100_n1-6.txt	95	33267	11452	26729	4914	6538
b_1_20_s_100_n1-6.txt	90	33267	17553	22717	7003	10550
b_1_20_s_100_n1-6.txt	85	33267	22052	21087	9872	12180
b_1_20_s_100_n1-12.txt	100	105570	15072	97055	6557	8515
b_1_20_s_100_n1-12.txt	95	105570	20434	93982	8846	11588
b_1_20_s_100_n1-12.txt	90	105570	30858	87863	13151	17707
b_1_20_s_100_n1-12.txt	85	105570	41158	83150	18738	22420
b_1_20_s_100_n1-24.txt	100	191834	41938	175876	25980	15958
b_1_20_s_100_n1-24.txt	95	191834	55643	169024	32833	22810
b_1_20_s_100_n1-24.txt	90	191834	84012	155138	47316	36696
b_1_20_s_100_n1-24.txt	85	191834	113100	136534	57800	55300
b_1_10_s_120_n1-6.txt	120	33267	7725	29065	523	4202
b_1_10_s_120_n1-6.txt	115	33267	11763	26586	5082	6681
b_1_10_s_120_n1-6.txt	110	33267	11352	26547	4632	6720
b_1_10_s_150_n1-6.txt	150	33267	6905	28813	2451	4454
b_1_10_s_150_n1-6.txt	145	33267	9543	27153	3429	6114
b_1_10_s_150_n1-6.txt	140	33267	13827	24579	5139	8688
b_1_10_s_150_n1-6.txt	135	33267	17958	21744	6435	11523
b_1_10_s_150_n1-6.txt	130	33267	21384	19927	8044	13340
b_1_10_s_150_n1-6.txt	125	33267	24490	19236	10459	14031
b_1_10_s_180_n1-6.txt	170	33267	9834	27457	4024	5810
b_1_10_s_180_n1-6.txt	130	33267	38402	20142	25277	13125
b_1_10_s_180_n1-6.txt	120	33267	55779	19966	42478	13301
b_1_10_s_200_n1-6.txt	200	33267	5083	29798	1614	3469
b_1_10_s_200_n1-6.txt	195	33267	6700	28661	2094	4606
b_1_10_s_200_n1-6.txt	190	33267	8827	27516	3076	5751
b_1_10_s_200_n1-6.txt	170	33267	12593	25866	5192	7401
b_1_10_s_200_n1-6.txt	135	33267	48787	19987	35507	13280
b_1_10_s_200_n1-6.txt	130	33267	57787	19994	44514	13273

<

Содержание Назад Вперед