Головна сторiнка
eng
Наукова бібліотека ім. М. Максимовича UNDP in Ukraine
Увага! Відтепер можна отримати пластиковий читацький квиток також за адресою:
проспект академіка Глушкова 2, кім. 217.

Подробиці читайте тут.
Список містить (0 документів)
Ваше замовлення (0 книжок)
Перегляд стану та історії замовлень
Допомога

Назад Новий пошук

Опис документа:

Автор: Zavadskyi I.O.
Назва: A family of fast exact pattern matching algorithms
Видавництво: ВПЦ "Київський університет"
Рік:
Сторінок: Р. 71-76
Тип документу: Стаття
Головний документ: Вісник Київського національного університету імені Тараса Шевченка
Анотація:   Описано сімейство алгоритмів точного пошуку рядка в більшому текстовому масиві. В алгоритмах використовуються багатовимірні масиви з метою обробки кожної ітерації кількох послідовних пошукових вікон. Це дає змогу знизити часову складність у середньому за рахунок підвищення ємнісних витрат. Розглянуті алгоритми є ефективними для коротких шуканих рядків (від 3 до 16 символів) і алфавітів середнього розміру (найвища ефективність досягається для алфавітів, що містять близько 30-40 елементів). Для деяких значень пар значень (довжина шуканого рядка, розмір алфавіту) запропоновані алгоритми є ефективнішими в середньому за всі відомі на сьогодні алгоритми точного пошуку підрядка.
   A family of comparison-based exact pattern matching algorithms is described. They utilize multidimensional arrays in order to process more than one subsequent text window in each iteration of the search cycle. This approach leads to a lower average time complexity by the cost of space. The algorithms of this family perform well forshort patterns and middle alphabets. In such case the shift of the window by several pattern lengths at once is quite probable, which is the main factor of algorithm success. Our algorithms outperform the Boyer-Moore-Horspool algorithm, either in the& original version or with Sunday"s "Quick search" modification, in a wide area of pattern length / alphabet size plane. In some subareas the proposed algorithms are the fastest among all known exact pattern matching algorithms. Namely, they perform b&est when alphabet size is about 30-40 and pattern length is about 4-10. Such parameters are typical for search in natural language text databases.
  


З 31.12.2014 по 01.03.2015 Наукова бібліотека
читачів не обслуговує.



Вибачте, зараз проходить оновлення бази системи, тому пошук тимчасово недоступний.
Спробуйте будь ласка через 20 хвилин

Цей сайт створено за спiльною програмою UNDP та
Київського нацiонального унiверситету iменi Тараса Шевченка
проект УКР/99/005

© 2000-2010 yawd, irishka, levsha, alex