Исследование и разработка методов и алгоритмов обработки символьных массивов в базах данных тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Айткулов, Павел Григорьевич

• Айткулов, Павел Григорьевич
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Айткулов, Павел Григорьевич

ВВЕДЕНИЕ

1 Обзор

1.1 Алгоритмы работы со строками

1.2 Обзор алгоритмов точного поиска преобразования образца

1.3 Обзор суффиксных структур данных.

1.4 Обзор алгоритмов построения суффиксных массивов

1.5 Аналогия с отсортированной коллекцией.

1.6 Замечание по используемым структурам данным.

1.7 Основные понятия.

1.8 Обзор алгоритмов по изменению суффиксных структур данных

1.9 О 1ср и поиске минимума на отрезке.

2 Разработка алгоритмов обработки символьных массивов

2.1 Алгоритм последовательного построения суффиксного массива

2.1.1 Оценка алгоритмической сложности и затрат памяти

2.1.2 Преимущества алгоритма и недостатки алгоритма

2.2 Алгоритм блочного построения суффиксного массива

2.2.1 Оценка алгоритмической сложности и затрат памяти

2.2.2 Выбор блока

2.2.3 Преимущества и недостатки алгоритма.

2.3 Удаление подстроки.

2.3.1 Оценка алгоритма.

Введение диссертации (часть автореферата) на тему «Исследование и разработка методов и алгоритмов обработки символьных массивов в базах данных»

Актуальность работы. Работа в текстовом редакторе, поисковые запросы в базе данных, задачи в биоинформатике, лексический анализ программ требуют эффективных алгоритмов работы со строками1.

Задачи поиска образца в тексте используются в криптографии, различных разделах физики, сжатии данных, распознавании речи.

В конце 1970-х годов на стыке генетики и информатики появилась биоинформатика (или вычислительная биология). Длина генотипа человека составляет 3,2 миллиарда символов (нуклеотидов). Для обработки таких больших данных требуются эффективные алгоритмы вычислений на строках.

Существует два основных подхода в алгоритмах точного поиска образца : преобразование образца и суффиксные структуры данных2.

В первом подходе образец является статичным, а исходный текст динамичен. Для каждого поискового запроса требуется прочитать исходный текст заново.

Если исходный текст является статичным, то стоит воспользоваться суф-фиксными структурами данных. Поисковый запрос к таким структурам требует линейных от длины образца ресурсов (количество операций и паработе рассматриваются классические вычисления. В квантовых вычислениях имеется алгоритм Гровера [28] для быстрого поиска в неупорядоченной базе данных за 0(\/п). В классических вычислениях эффективность алгоритмов на строках означает время работы близкое к линейному.

2В области неточного поиска используются другие меюды, например, на основе п-грамм [40]. мять).

К недостаткам существующих алгоритмов построения суффиксных структур данных относится то, что для построения структуры требуется вся строка целиком. Это ограничивает использование суффиксных структур данных с потоковыми данными. Малое изменение строки приведет к полной перестройке суффиксной структуры.

При использовании суффиксных структур данных для индексации текстовых записей в базах данных малое изменение (добавление, удаление или изменение одной записи) приводит к полной перестройке индекса.

Целью работы является построение эффективных алгоритмов изменения суффиксных структур данных (суффиксных массивов), построение приложений для индексации текстовых записей в базах данных. Эффективность подразумевает линейные (близкие к линейным) затраты от длины изменившейся части строки.

Методы исследования. В работе применяются методы теории алгоритмов и сложности, амортизационного анализа, алгебры, динамического программирования. Используются алгоритмы и структуры данных из таких областей, как теория автоматов, теория графов, строковые алгоритмы.

Научная новизна. В работе построены алгоритмы модификации такой суффиксной структуры данных, как суффиксный массив. Построены алгоритмы потокового построения суффиксного массива и удаления подстроки из суффиксного массива. В отличие от существующих алгоритмов, в процессе работы алгоритма поддерживается массив наибольшего общего префикса 1ср. Построен алгоритм препроцессинга (создание всех дополнительных структур данных на основе текущего суффиксного массива и строки).

Индексация строковых полей в базе данных и имен файлов в файловой системе применена на практике.

Построенные алгоритмы позволяют решать задачу о наибольшей общей подстроке для динамического случая для одной, двух и к строк. Были известны решения только для статического случая.

Построен алгоритм динамического поиска лексикографически наименьшего суффикса, лексикографически наименьшего циклического сдвига. Для поиска лексикографически наименьшего суффикса были известны потоковые решения, а для задачи лексикографически наименьшего циклического сдвига только решения для статического случая.

Построено приложение к архивации. Предлагается использовать потоковое построение суффиксных массивов для ¿^-факторизации. Построено приложение к технике «скользящего окна» (поддержка суффиксного массива только для последних символов потока).

Достоверность результатов обеспечивается строгостью доказательств и подтверждается практическими результатами реализованных алгоритмов.

Практическая и теоретическая ценность. Результаты, полученные в диссертационной работе, позволяют динамически изменять суффиксные массивы, индексировать текстовые записи в базах данных и имен файлов в файловой системе (добавление, удаление и изменение объекта). Решен класс динамических задач (динамическая задача о наибольшей общей подстроке, лексикографически наименьший суффикс, циклический сдвиг). Построено приложение к архивации: предлагается использовать суффиксные массивы в качестве внутренней структуры данных для алгоритма потокового сжатия Лемпеля-Зива.

Реализация и внедрение результатов работы. Результаты исследования (потоковое построение суффиксных массивов) внедрены в практическую деятельность и используются в программных продуктах ОАО «НК Роснефть», что подтверждается актом о внедрении результатов диссертационной работы.

На защиту выносятся следующие основные результаты и положения:

1. Алгоритм последовательного построения суффиксного массива.

2. Алгоритм блочного построения суффиксного массива.

3. Алгоритм удаления подстроки из суффиксного массива.

4. Приложение для индексации текстовых записей в базах данных.

5. Алгоритм динамического поиска наибольшей общей подстроки для к строк.

6. Алгоритм динамического поиска лексикографически наименьшего суффикса, лексикографически наименьшего циклического сдвига.

7. Приложение к архивации; использование в технике «скользящего окна».

Апробация работы. Результаты работы докладывались и обсуждались на семинаре «Теоретические основы и приложения информатики» г. Ижевск, 2009 г.; VI всероссийской школе-семинаре молодых ученых «Управление большими системами» г. Ижевск, 2009 г.; семинаре в ИПУ РАН г. Москва 2010 г.; VII всероссийской школе-семинаре молодых ученых «Управление большими системами» г. Пермь, 2010 г.;

Публикации результатов исследования. Основные результаты научных исследований по теме диссертации содержатся в 4 печатных работах [1, 2, 3, 4], в том числе 2 - в изданиях, рекомендованных ВАК РФ.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы и приложения. Объем работы составляет 97 страниц текста, включая 12 рисунков. Библиография включает 57 наименований.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Айткулов, Павел Григорьевич

ЗАКЛЮЧЕНИЕ

В работе построены алгоритмы последовательного построения суффикс-ного массива, блочного построения суффиксиого массива, удаления блока из суффиксного массива.

В алгоритме последовательного построения суффиксного массива производится модификация суффиксного массива при добавлении одного символа к текущей строке. Асимптотика алгоритма составляет для 1ср-естественных языков 0(1од2(п)), для /ф-регулярных - 0{п1од2{п)). Последовательное добавление т символов для /ср-регулярных строк в худшем случае требует 0(т2 1од2(п)) операций.

В алгоритме блочного построения суффиксного массива производится модификация суффиксного массива при добавлении строки. Добавление строки размером т требует 0{гп1од2{п)) операций.

В алгоритме удаления блока из суффиксного массива производится модификация суффиксного массива при удалении подстроки. Удаление подстроки размером т требует 0(т1од2(п)) операций.

Во всех построенных алгоритмах затраты на память составляют 0(п).

Построенные алгоритмы позволяют работать с потоковыми данными.

В отличие от существующих алгоритмов, в процессе работы поддерживается массив наибольших префиксов 1ср, имеется возможность преироцес-спнга.

Построено практическое применение для индексации имен файлов в файловой системе и текстовых записей в базах данных.

В работе решена динамическая задача о наибольшей общей подстроки (для одной строки, для двух строк и общая задача для к строк). Были известны решения только для статического случая.

Решена динамическая задача поиска лексикографически наименьшего суффикса, лексикографически наименьшего циклического сдвига. Для поиска лексикографически наименьшего суффикса были известны потоковые решения, а для задачи лексикографически наименьшего циклического сдвига только решения для статического случая.

Построено приложение к архивации. Предлагается использовать потоковое построение суффиксных массивов к ¿^-факторизации. Построено приложение к технике «скользящего окна» (поддержка суффиксного массива только для последних символов потока).

Список литературы диссертационного исследования кандидат технических наук Айткулов, Павел Григорьевич, 2010 год

1. Айткулов П. Г. Блочное построение суффиксного массива // Труды б Всероссийской школы-семинара молодых ученых. Управление большими системами. Том 1. Ижевск, 2009. С. 17-26.

2. Айткулов П. Г. Обработка символьных массивов // Управление большими системами. Выпуск 28. М.: ИПУ РАН, 2010. С. 126-178.

3. Айткулов П. Г. Динамический поиск лексикографически наименьшего суффикса и циклического сдвига // Труды 2 Всероссийской научно-практической конференции «Перспективы развития информационных технологий». Новосибирск, 2010. С. 10-12.

4. Айткулов П. Г. Приложение потокового построения суффикспых массивов к архивированию // Материалы VII Всероссийской школы-конференции молодых ученых. Управление большими системами. Том 2. Пермь, 2010. С. 193-197.

5. Ахо А., Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

6. Вирт Н. Алгоритмы и структуры данных. СПб.: Невский диалект, 2008.

7. Гасфилд Д. Строки, деревья, последовательности в алгоритмах. -СПб.: Невский Диалект; БХВ-Петербург, 2003.

8. Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ-Петербург, 2003.

9. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 1999.

10. Препарата Ф., Шеймос М. Вычислительная геометрия: введение. -М.: Мир, 1989.

11. Слисенко А. О. Нахождение в реальное время всех периодичностей в слове И Доклады АН СССР. 1980. - Т. 251. - С. 48-51.

12. Слисенко А. О. Поиск периодичностей и идентификация подслое в реальное время // Зап. научн. сем. ЛОМИ. 1981. - Т. 5. - С. 62-173.

13. Слисенко А. О. Распознавание предиката симметрии многоголовчатыми машинами Тьюринга со входом // Труды Мат. института АН СССР. 1973. - Т. 129. - С. 30-202.

14. Смит Б. Методы и алгоритмы вычислений на строках. Вильяме, 2006.

15. Aho A., Corasick М. Efficient string matching: an aid to bibliographic search // Communications of the ACM. 1975. - Vol. 18. - P. 333-340.

16. Appel A., Jacobsen G. The World's Fastest Scrabble Program // Communications of the ACM. 1988. -P. 572-578.

17. Baase S. Computer Algorithms. 2nd ed. Reading, MA: Addison-Wesley, 1988.

18. Boyer R. S., Moore J. S. A fast string searching algorithm // Comm. ACM. 1977. - Vol. 20. - R 762-772.

19. Charras C., Lecroq T. Handbook of Exact String-Matching Algorithms, 2004.

20. Duval J.-P. Factorizing words over an ordered alphabet // Journal Algorithms. 1983. -Vol. 4. - P. 363-381.

21. Farach M. Optimal suffix tree construction with large alphabets //In Proc. IEEE 38th Annual Symposium on Foundations of Computer Science. -1997. P. 137-143.

22. Farach M., Muthukrishnan S. Optimal logarithmic time randomized suffix tree construction //In Proc. IEEE 23th International Conference on Automata, Languages and Programming. 1996. - P. 550-561.

23. Farach M., Ferragina P., Muthukrishnan S. On the sorting-complexity of suffix tree construction // J. ACM. 2000. - Vol. 47(6). -P. 987-1011.

24. Ferragina P., Grossi R. Fast incremental text editing // Proceedings of the sixth annual ACM-SIAM Symposium on Discrete Algorithms. -1995. -P. 531-540.

25. Ferragina P., Fisher J. Suffix array on words // Combinatorial pattern matching: 18th annual symposium. -2007. -P. 328-339.

26. Gerlach W. Dynamic FM-Index for a collection of texts with application to space-efficient construction of the compressed suffix array, Master's thesis, Universität Bielefeld, Germany, 2007.

27. Gwehenberger G. Anwendung einer binaren Verweiskettenmethode beim Außau von Listen. Elektronische Rechenanlagen 1968. -Vol 10, -P. 223226

28. Grover L.K. A fast quantum mechanical algorithm for database search // Proceedings, 28th Annual ACM Symposium on the Theory of Computing. 1996. P. 212

29. Hubbard T.J. P., Lest A.M., Tramontane A. Gathering item into the fold // Nature Structural Biology. April, 1996. - Vol. 4. - P. 313.

30. Karkkainen J., Sanders P., Simple Linear Work Suffix Array Construction // Proceedings of the 30th International Colloquium on Automata, Languages and Programming, LNCS 2719, Springer, 2003. -P. 943-955.

31. Karkkainen J., Fast BWT in Small Space by Blockwise Suffix Sorting // Theoretical Computer Science, 2006.

32. Kasai T., Lee G., Arimura H., Arikawa S., Park K. Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications // CPM. 2001. - P. 181-192.

33. Kitajima J. P., Navarro G., Ribeiro B., Ziviani N. Distributed Generation of Suffix Arrays: a Quicksort-Based Approach // Proceedings of the 4th South American Workshop on String Processing, Valparaiso, Chile, 1997. -P. 53-59.

34. Karp R., Rabin M. Efficient randomized pattern matching algorithms // IBM J. Res. Development. 1987. - Vol. 31. - P. 246-260.

35. Knuth D. E., Morris J. H., Pratt V. B. Fast pattern matching in strings // SIAM Journal on Computing. 1977. - Vol. 6. - P. 323-350.

36. Knuth D. E. The Art of Computer Programming, Volume 2: Sorting and Searching, Second Edition. Addison-Wesley, 1997.

37. Ko P., Aluru S., Space-efficient linear time construction of suffix arrays, Proceedings of the 14th Annual Symposium on Combinatorial Pattern Matching, 2003. - P. 200-210.

38. Larsson J. Extended application of suffix trees to data compression. Data Compression Conference. 1996.

39. Manber U., Mayers G. Suffix arrays: a new method for on-line string searches // SIAM Journal on Computing. 1993. - №22. - P. 953-948.

40. Manning C., Schutze H. Foundations of Statistical Natural Language Processing, MIT Press. 1999.

41. McCreight E. M. A Space-Economical Suffix Tree Construction Algorithm // Journal of the ACM. 1976. - Vol. 23(2). - P. 262-272.

42. Morrison D. PATRICIA-Practical Algorithm To Retrieve Information Coded in Alphanumeric // Journal of ACM. 1968. -Vol. 15(4). - P. 514534.

43. Navarro G., Kitajima J. P., Ribeiro B., Ziviani N., Distributed Generation of Suffix Arrays // Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching, LNCS 1264. 1997. - P. 102-115.

44. Kim D. K, Sim J., Park H., Park K., Linear-time construction of suffix arrays // Proceedings of the 14th Annual Symposium on Combinatorial Pattern Matching, 2003 - P. 186-199.

45. Russo L., Navarro G., Oliveira A., Fully-compressed suffix trees // Proceedings of the 8th Latin American conference on Theoretical informatics, LNCS. 2008. -P. 362-373.

46. Rytter W. A correct preprocessing algorithm for Boyer-Moore string searching // SIAM J. Comput. 1980. - Vol. 9. - P. 509-512.

47. Salson M., Lecroq T. Leonard M., Mouchard L. Dynamic extended, suffix arrays // Journal of Discrete Algorithms. 2010. -Vol. 8. -P.241-257.

48. Salson M., Lecroq Т., Leonard M., Mouchard L. A ■Four-Stage Algorithm for Updating a Burrows- Wheeler Transform // Theoretical Computer Science, 2009.

49. Shibuya Т., Kurochkin I. Match chaining algorithm for cDNA Mapping // Algorithms in Bioinformatics: Third International Workshop, Budapest, WABI, 2003.

50. Ukkonen E. On-line construction of suffix trees // Algorithmica. 1995. - Vol. 14(3). - P. 249-260.

51. Weiner P. Linear pattern matching algorithm // 14th Annual IEEE Symposium on Switching and Automata Theory. 1973. - P. 1-11.

52. Welch T. A Technique for High Performance Data Compression // IEEE Computer. 1984. - Vol. 17 - P. 8-19.

53. Ziv J., Lempel A. A Universal Algorithm for Sequential Data Compression // IEEE Transactions on Information Theory. 1977. -Vol. 23(3). -P. 337-343.

54. Система ConQAT электронный ресурс] http: //conqat. cs. turn. edu/ index.php/ConQAT (дата обращения 13.08.2010).

55. Система Simian электронный ресурс] http: //www. redhillconsulting.com.au/products/simian/ (дата обращения 13.08.2010).

56. Система РМБ электронный ресурс] http://pmd.sourceforge.net/ (дата обращения 13.08.2010).

57. ТЭеагсЬ, индекс для полнотекснового поиска в Postgгes электронный ресурс] http://www.sai.msu.su/~megera/postgres/gist/ tsearch/V2/ (дата обращения 13.08.2010).