Скачать презентацию
Идет загрузка презентации. Пожалуйста, подождите
Презентация была опубликована 10 лет назад пользователемПотап Завадский
1 Эффективное создание текстовых индексов Веретенников Александр
2 CLB дерево Веретенников А. Б., Лукач Ю. С. Еще один способ индексации больших массивов текстов. Известия Уральского государственного университета. Серия «Компьютерные науки», 2006.
3 CLB-дерево B-дерево … … Таблица для слов из словаря … Вспомогательные таблицы
4 CLB-индекс CLB-дерево … Репозитарий Атрибуты документов Настройки и информация об остальных компонентах Индекс похожих документов
5 Система индексирования Ядро Модуль поддержки форматов файлов Морфология COM сервер Распознавание кодировки Модуль репозитария Модуль атрибутов документов
6 Архивы и документы RTF PDF CHM ZIP Модуль поддержки форматов … Модули DLL Модули JAVA (JNI)
7 Форматы файлов RTF, PDF, CHM, HTML ZIP, CAB, RAR, 7Z, ARJ, TAR, … UNICODE, UTF8, CP1251, ASCII, KOI8
8 Теоретические результаты d – доля известных слов в текстах, т. е. тех, которые входят в словарь R – текущее количество слов в CLB- дереве H – размер страницы B-дерева, K – размер кластера.
9 Теоретические результаты Теорема 1: Вставка N слов в CLB- индекс потребует O(dN/K + (1-d)N(1+ log H ((1-d)(R+N)))) обращений к внешней памяти.
10 Теоретические результаты Теорема 2: Поиск фразы из N слов в CLB-индексе потребует O(N(log H ((1-d)R) + occ/K) обращений к внешней памяти, где occ – количество вхождений данных слов в текстах.
11 Теоретические результаты Поиск с помощью инвертированных файлов O(N(occ/K)), у нас O(N(log H ((1-d)R) + occ/K), но N(log H ((1-d)R) – мало по сравнению с N(occ/K)
12 Эксперименты 25 гигабайт текста ( файлов) индексируется за 3 часа 3 млрд. слов. 3,6 млрд. форм слов. E6700, 2гб RAM. 21,5 гб чистого текста.
13 Эксперименты 75 гигабайт текста ( файлов) индексируется за 10 часов 9,8 млрд. слов 12,3 млрд. форм слов P4, 2гб RAM. 70 гб чистого текста.
14 Литература Prywes, N. S., Gray, H. J. The organization of a Multilist-type associative memory. IEEE Trans. on Communication and Electronics, 68 (1963), Ferragina, P., Grossi, R. The string B-tree: a new data structure for string search in external memory and its applications. Journal of the ACM, 46, 2 (1999), Bayer, R., McCreight, E. Organization and maintenance of large ordered indexes. Acta Informatica 1, 3 (1972), Веретенников А. Б., Лукач Ю. С. Еще один способ индексации больших массивов текстов. Известия Уральского государственного университета. Серия «Компьютерные науки», Лукач Ю. С. Быстрый морфологический анализ флективных языков. Международная алгебраическая конференция: К 100- летию со дня рождения П. Г. Конторовича и 70-летию Л. Н. Шеврина. Тез. докл. Екатеринбург: Изд-во Урал. ун-та, 2005, с
Еще похожие презентации в нашем архиве:
© 2024 MyShared Inc.
All rights reserved.