Signaturní soubory se signaturami proměnné délky

Signature files with variable-length signatures

dissertation

Czech

Tato práce se zabývá zpracováním informací a vyhledáváním v nich. Zaměřuje se na textové informace a vyhledávání pomocí signaturních souborů. Hlavní úsilí je směřováno k navržení nové efektivní vyhledávácí metody. Toto může být dosaženo pouze při důkladné znalosti vlastností dat, ve kterých se bude vyhledávat. Proto je proveden podrobný rozbor vlastností textových dat. Pro některé vlastnosti jsou pak navrženy nové analytické aproximace. Není zapomenuto ani na české dokumenty, které mají své specifické vlastnosti. Pro textová data je potřeba také zvolit vhodnou metodu pro vytváření signatur. Metody popsané v literatuře byly analyzovány a patřičně modifikovány pro naše požadavky. Bylo vyzkoušeno mnoho organizací signatur, ale žádná nesplňovala náročné požadavky současných systémů. Proto je navržena nová metoda organizace, která je rychlá při vytváření i při vyhodnocování dotazu, vytvořený pomocný soubor je malý a vyhledávání lze snadno paralelizovat. Změnou několika parametrů lze plynule přejít od efektivnosti invertovaných souborů při vyhledávání až po velkou datovou kompresi signaturních souborů. Pro všechny metody organizací jsou navrženy analytické modely. Tato práce není pouze prací teoretickou, ale návrhy a vytvořené modely jsou také ověřovány experimentálně.

There is a growing need for fast retrieval of information from an enormous number of existing text documents. Current search engines are using intermediary indexing structures. Inverted and signature files are among the most common structures. This work deals with signatures of variable length created by a compression method and specializes in retrieval from text documents. A good knowledge about the data used is necessary, which is why text collections have been analyzed. Text collections are divided into documents. Most search engines work with documents considering only one word occurrence within the document, not the number of occurrences. Such cases were analysed and based on that, an approximate mathematical relation has been developed. The relation, that is the first important result of this work, is between the word occurrence frequency and the word rank in a text's wordlist ordered by decreasing frequency. The right choice of convenient signature extraction method and a corresponding signature file organization is important for creating efficient signature file access methods. Sizes of individual text documents vary significantly and the best way to avoid this problem is to use compression-based extraction methods. Such methods are described in the literature. This work proposes new analytic performance models expressing the dependency of a query processing time on the query weight. The proposed models have been experimentally verified. For creating signatures a quality hashing function is important. It should be fast, easy to calculate and it should distribute words uniformly to hashing space. Two hashing functions have been proposed and both satisfy these requirements. Based on a comprehensive study of compression-based methods, a new two-level organization has been proposed. It is simple and preserves sequential ordering. Therefore it does not increase insertion time and it can be simply parallelized. The second important result of this work is a new signature organization method called Dynamic S-index (DSI). This method makes index creation and query processing very fast, the created file is small, and the processes can easily be run in parallel. Properties of DSI can be controlled by means of several parameters in such a way that they vary from properties of an inverted file to properties of a signature file. Experiments show very good results for retrieval from text documents and therefore DSI could be used as an alternative or complementary organization structure to inverted files. Computational complexity models have been developed and verified experimentally for both proposed signature organization methods.

Vyhledávání informace, signaturní soubor, invertovaný soubor, Zipfův zákon, dynamický S-index

Information retrieval, signature file, inverted file, Zipf's law, dynamic S-index

KORČÁK, Z.

8. 10. 2002

Fakulta informačních technologií VUT v Brně

Brno

76

http://www.fit.vutbr.cz/~zendulka/theses/zkorcak.pdf