Эффективное создание текстовых индексов Веретенников Александр.

Презентация:



Advertisements
Похожие презентации
Создание легко обновляемых текстовых индексов Веретенников А. Б.
Advertisements

Полнотекстовый индекс для часто обновляющихся библиотек Веретенников А. Б. Уральский федеральный университет им. Б. Н. Ельцина
Электронная Библиотека Президента Полнотекстовый поиск на базе iFTS SQL Server Июнь 2009| MSC.
Архивация – это способ упаковки файлов и папок, при которой они теряют значительную часть своего объёма. Происходит это вследствие того, что повторяющиеся.
ТЕКСТОВАЯ ИНФОРМАЦИЯ И КОМПЬЮТЕР Представление символов Таблица кодировки Код ASCII 256символов 1 символ – 1 байт стандартная часть коды 0 – 127 альтернативная.
Электронный задачник по программированию для системы 1С:Предприятие М. Э. Абрамян, М. Ю. Беренкеева Южный федеральный университет, факультет математики,
Информационно- поисковая система «Архив документов»
Файловая система. Файл – это логически связанная совокупность данных или программ, для размещения которой во внешней памяти выделяется именованная область.
Система Антиплагиат.РГБ: результаты работы и новые возможности Десятая, юбилейная, международная научно-практическая конференция "ЭЛЕКТРОННЫЙ ВЕК КУЛЬТУРЫ"
Информационно-поисковые системы. Сычев А.В г. 1 Спамдексирование Воронежский государственный университет Факультет компьютерных наук Кафедра информационных.
ВОЗМОЖНОСТИ ПРЕПОДАВАТЕЛЕЙ ПО ФОРМИРОВАНИЮ УЧЕБНОГО КОНТЕНТА В ПРОГРАММЕ eAuthor 3.1 Выполнил: Студент группы С-95 Соболевский А.А.
ПОНЯТИЕ ТЕКСТОВОГО ФАЙЛА И ТЕКСТОВОГО ДОКУМЕНТА. НАЗНАЧЕНИЕ ТЕКСТОВЫХ РЕДАКТОРОВ И ИХ ТИПЫ. ИНТЕРФЕЙС ТЕКСТОВОГО РЕДАКТОРА И ИЗМЕНЕНИЕ ЕГО НАСТРОЕК.
2 х =N Х – количество бит, отводимых на один символ N – мощность алфавита.
ТЕКСТЫ В КОМПЬЮТЕРНОЙ ПАМЯТИ.. С помощью компьютера можно создавать текстовые документы и хранить их на магнитных носителях в виде файлов. С помощью компьютера.
ПОНЯТИЕ ТЕКСТОВОГО ФАЙЛА И ТЕКСТОВОГО ДОКУМЕНТА. НАЗНАЧЕНИЕ ТЕКСТОВЫХ РЕДАКТОРОВ И ИХ ТИПЫ. ИНТЕРФЕЙС ТЕКСТОВОГО РЕДАКТОРА И ИЗМЕНЕНИЕ ЕГО НАСТРОЕК.
Тексты в компьютерной памяти Презентация к уроку «Тексты в компьютерной памяти» Подготовила Артемова Е.В. Учитель информатики и ИКТ МБОУ «СОШ 8 г. Петровска.
Цели работы: Рассмотреть сохранение документа в различных текстовых форматах. Печать документа научиться включать в текстовый документ формулы и графические.
A CITY Дизайн Описание Спецификация. 2 Преимущества AirBook City: - Технология экрана E-Ink Pearl - Диагональ экрана 6 - Размеры 168 х 116 х 8 мм - Вес.
ТЕКСТЫ В КОМПЬЮТЕРНОЙ ПАМЯТИ. С помощью компьютера можно создавать текстовые документы и хранить их на магнитных носителях в виде файлов.
Антивирус Касперского® Personal Pro. Антивирус Касперского® 5.0 Personal Pro Интерфейс пользователя Простой графический интерфейс с минимально необходимым.
Транксрипт:

Эффективное создание текстовых индексов Веретенников Александр

CLB дерево Веретенников А. Б., Лукач Ю. С. Еще один способ индексации больших массивов текстов. Известия Уральского государственного университета. Серия «Компьютерные науки», 2006.

CLB-дерево B-дерево … … Таблица для слов из словаря … Вспомогательные таблицы

CLB-индекс CLB-дерево … Репозитарий Атрибуты документов Настройки и информация об остальных компонентах Индекс похожих документов

Система индексирования Ядро Модуль поддержки форматов файлов Морфология COM сервер Распознавание кодировки Модуль репозитария Модуль атрибутов документов

Архивы и документы RTF PDF CHM ZIP Модуль поддержки форматов … Модули DLL Модули JAVA (JNI)

Форматы файлов RTF, PDF, CHM, HTML ZIP, CAB, RAR, 7Z, ARJ, TAR, … UNICODE, UTF8, CP1251, ASCII, KOI8

Теоретические результаты d – доля известных слов в текстах, т. е. тех, которые входят в словарь R – текущее количество слов в CLB- дереве H – размер страницы B-дерева, K – размер кластера.

Теоретические результаты Теорема 1: Вставка N слов в CLB- индекс потребует O(dN/K + (1-d)N(1+ log H ((1-d)(R+N)))) обращений к внешней памяти.

Теоретические результаты Теорема 2: Поиск фразы из N слов в CLB-индексе потребует O(N(log H ((1-d)R) + occ/K) обращений к внешней памяти, где occ – количество вхождений данных слов в текстах.

Теоретические результаты Поиск с помощью инвертированных файлов O(N(occ/K)), у нас O(N(log H ((1-d)R) + occ/K), но N(log H ((1-d)R) – мало по сравнению с N(occ/K)

Эксперименты 25 гигабайт текста ( файлов) индексируется за 3 часа 3 млрд. слов. 3,6 млрд. форм слов. E6700, 2гб RAM. 21,5 гб чистого текста.

Эксперименты 75 гигабайт текста ( файлов) индексируется за 10 часов 9,8 млрд. слов 12,3 млрд. форм слов P4, 2гб RAM. 70 гб чистого текста.

Литература 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, с