Показать сокращенную информацию
Combined string searching algorithm based on knuth-morris- pratt and boyer-moore algorithms
Автор | Царев, Р. Ю. | |
Автор | Черниговский, А. С. | |
Автор | Царева, Е. А. | |
Автор | Брезицкая, В. В. | |
Автор | Никифоров, А. Ю. | |
Автор | Смирнов, Н. А. | |
Дата внесения | 2016-11-11T08:52:06Z | |
Дата, когда ресурс стал доступен | 2016-11-11T08:52:06Z | |
Дата публикации | 2016-07 | |
Библиографическое описание | Царев, Р. Ю. Combined string searching algorithm based on knuth-morris- pratt and boyer-moore algorithms [Текст] / Р. Ю. Царев, А. С. Черниговский, Е. А. Царева, В. В. Брезицкая, А. Ю. Никифоров, Н. А. Смирнов // IOP Conference Series: Materials Science and Engineering. — 2016. — Т. 122 (№ 1). — . | |
URI (для ссылок/цитирований) | https://elib.sfu-kras.ru/handle/2311/27966 | |
Аннотация | The string searching task can be classified as a classic information processing task. Users either encounter the solution of this task while working with text processors or browsers, employing standard built-in tools, or this task is solved unseen by the users, while they are working with various computer programmes. Nowadays there are many algorithms for solving the string searching problem. The main criterion of these algorithms' effectiveness is searching speed. The larger the shift of the pattern relative to the string in case of pattern and string characters' mismatch is, the higher is the algorithm running speed. This article offers a combined algorithm, which has been developed on the basis of well-known Knuth-Morris-Pratt and Boyer-Moore string searching algorithms. These algorithms are based on two different basic principles of pattern matching. Knuth-Morris-Pratt algorithm is based upon forward pattern matching and Boyer-Moore is based upon backward pattern matching. Having united these two algorithms, the combined algorithm allows acquiring the larger shift in case of pattern and string characters' mismatch. The article provides an example, which illustrates the results of Boyer-Moore and Knuth-Morris- Pratt algorithms and combined algorithm's work and shows advantage of the latter in solving string searching problem. | |
Ссылка на другой сайт | http://iopscience.iop.org/article/10.1088/1757-899X/122/1/012034/meta | |
Тема | basic principles | |
Тема | Boyer-Moore | |
Тема | Boyer-Moore algorithms | |
Тема | combined algorithms | |
Тема | running speed | |
Тема | searching speed | |
Тема | string-searching | |
Название | Combined string searching algorithm based on knuth-morris- pratt and boyer-moore algorithms | |
Тип | Journal Article | |
Тип | Published Journal Article | |
ГРНТИ | 20.23 | |
Дата обновления | 2016-11-11T08:52:05Z | |
DOI | 10.1088/1757-899X/122/1/012034 | |
Институт | Политехнический институт | |
Институт | Институт космических и информационных технологий | |
Подразделение | Кафедра технологических машин и оборудования | |
Подразделение | Кафедра информатики | |
Журнал | IOP Conference Series: Materials Science and Engineering | |
Квартиль журнала в Scopus | Q4 |