Compact representation of URL collections with fast access

Abstract

Efektywna reprezentacja słownika fraz tekstowych jest klasycznym problemem mającym zastosowania m.in. w wyszukiwarkach internetowych i kontroli pisowni. Zazwyczaj słownik jest stosunkowo mały w stosunku do tekstu, z którego zebrano kolekcję fraz (słów), jednak w niektórych zastosowaniach liczba fraz może być ogromna, co praktycznie zmusza do wykorzystania kompresji. Jednym z takich przykładów są kolekcje adresów dokumentów internetowych, tj. kolekcje URL. Duże kolekcje URL wykorzystywane są np. w analizie dużych wycinków tzw. grafu webowego. W niniejszej pracy proponujemy efektywny algorytm kompresji ułożonych leksykograficznie kolekcji URL, z obsługą zapytań typu extract. Efficient representation of a string dictionary is a well-known problem with applications e.g. in Web searchers and spellchecking. Traditionally, the dictionary is relatively minor compared to the text from which the terms (words) are collected, but in several applications the number of dictionary items is huge, making a compressed format highly desirable. One of those cases are document addresses on the Internet, i.e., their URLs. Large collections of URLs are useful e.g. in analyses of (possibly large portions of) the Web graph. In this work we present an efficient compression algorithm for lexicogra-phically ordered collections of URLs, supporting extract queries.