?
Cross-Document Pattern Matching
P. 196-207.
Kucherov G., Nekrich Y., Стариковская Т. А.
We study a new variant of the string matching problem called {\em cross-document string matching}, which is the problem of indexing a collection of documents to support an efficient search for a pattern in a selected document, where the pattern itself is a substring of another document. Several variants of this problem are considered, and efficient linear-space solutions are proposed with query time bounds that either do not depend at all on the pattern size or depend on it in a very limited way (doubly logarithmic). As a side result, we propose an improved solution to the {\em weighted level ancestor} problem.
Язык:
английский
В книге
Vol. 7354: Proceedings of the 23rd Symposium on Combinatorial Pattern Matching. , Berlin : Springer, 2012
Babenko M., Kolesnichenko I., Стариковская Т. А., , in : Lecture Notes in Computer Science. Vol. 7922: Proceedings of the 24th Symposium on Combinatorial Pattern Matching.: Berlin : Springer, 2013. P. 28-37.
Lexicographically minimal and lexicographically maximal suffixes of a string are fundamental notions of stringology. It is well known that the lexicographically minimal and maximal suffixes of a given string S can be computed in linear time and space by constructing a suffix tree or a suffix array of S. Here we consider the case when ...
Добавлено: 30 октября 2013 г.
Kucherov G., Nekrich Y., Стариковская Т. А., , in : Lecture Notes in Computer Science. Vol. 7608: Proceedings of the 19th International Symposium on String Processing and Information Retrieval.: Berlin : Springer, 2012. P. 307-317.
We study the following three problems of computing generic or discriminating words for a given collection of documents. Given a pattern $P$ and a threshold $d$, we want to report (i) all longest extensions of $P$ which occur in at least $d$ documents, (ii) all shortest extensions of $P$ which occur in less than $d$ ...
Добавлено: 30 октября 2013 г.
Vildhoj H. W., Стариковская Т. А., , in : Lecture Notes in Computer Science. Vol. 7922: Proceedings of the 24th Symposium on Combinatorial Pattern Matching.: Berlin : Springer, 2013. P. 223-234.
Lexicographically minimal and lexicographically maximal suffixes of a string are fundamental notions of stringology. It is well known that the lexicographically minimal and maximal suffixes of a given string $S$ can be computed in linear time and space by constructing a suffix tree or a suffix array of $S$. Here we consider the case when ...
Добавлено: 30 октября 2013 г.
Бабенко М. А., Стариковская Т. А., , in : Lecture Notes in Computer Science. Vol. 5010: Proceedings of the Third International Computer Science Symposium in Russia.: Berlin : Springer, 2008. P. 64-75.
Given a set of $N$ strings $A = \set{\alpha_1, \ldots, \alpha_N}$ of total length $n$ over alphabet~$\Sigma$ one may ask to find, for a fixed integer $K$, $2 \le K \le N$, the longest substring $\beta$ that appears in at least $K$ strings in $A$. It is known that this problem can be solved in ...
Добавлено: 30 октября 2013 г.
Babenko A., Lempitsky V., , in : Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2012). : Providence : IEEE, 2012. P. 3069-3076.
Добавлено: 1 октября 2014 г.
Полякова О. А., Пермь : Издательство Пермского национального исследовательского политехнического университета, 2019
Рассмотрены вопросы применения основных принципов структурного программирования в сложных программах системах на языке высокого уровня С++, которые демонстрируются на содержательных примерах. ...
Добавлено: 31 августа 2020 г.
Бабенко М. А., Стариковская Т. А., Проблемы передачи информации 2011 Т. 47 № 1 С. 28-33
Описан алгоритм, решающий задачу нахождения приближенной максимальной общей подстроки двух строк $\alpha_1$ и $\alpha_2$ за время $O(\abs{\alpha_1} \abs{\alpha_2})$ с использованием $O(\abs{\alpha_1})$ дополнительной памяти. При обращении к строке $\alpha_2$ алгоритм читает ее только \emph{слева направо, начиная с первого символа}. Используется RAM-модель вычислений. ...
Добавлено: 30 октября 2013 г.
Berlin : Springer, 2012
This book constitutes the refereed proceedings of the 23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012, held in Helsinki, Finalnd, in July 2012.
The 33 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 60 submissions. The papers address issues of searching and matching strings and more complicated patterns ...
Добавлено: 30 октября 2013 г.
Галимуллин М. Ф., Калишенко Е. Л., Рапоткин Н. А., Известия Санкт-Петербургского государственного электротехнического университета ЛЭТИ 2016 № 7 С. 13-23
Рассматриваются некоторые сценарии использования конкурентных структур данных, показывающие повышение производительности при увеличении времени работы одного потока, которому остальные потоки делегируют свои задачи. Данный подход получил название flat-combining (FC) [1]. Представлены несколько разработанных стратегий синхронизации, описаны их преимущества и область применения. ...
Добавлено: 1 ноября 2018 г.
Бабкина Т. С., Демидовский А. В., Бабкин Э. А., International Journal of Big Data Intelligence 2018 Vol. 5 No. 3 P. 143-155
В этой работе представлены два новых подхода к решению классической NP-трудной задачи по поиску максимальной клики. Эта задача, которая часто возникает в области управления информацией, включая проектирование структур баз данных и обработку больших объемов данных. В нашем исследовании мы фокусируемся на решении этой задачи с использованием парадигмы искусственных нейронных сетей. Первый подход объединяет парадигму искусственных нейро-сетей и ...
Добавлено: 3 октября 2018 г.
Kolpakov R. M., Kucherov G., Стариковская Т. А., , in : Proceedings of the First International Conference on Data Compression, Communications and Processing. : NY : IEEE Computer Society, 2013. P. 92-97.
We consider a compact text index based on evenly spaced sparse suffix trees of a text \cite{KU-96}. Such a tree is defined by partitioning the text into blocks of equal size and constructing the suffix tree only for those suffixes that start at block boundaries. We propose a new pattern matching algorithm on this structure. ...
Добавлено: 30 октября 2013 г.
Таганрог : Издательство ЮФУ, 2015
Сборник составлен по материалам VI Международной научно-практической конференции "Технологии разработки информационных систем", состоявшейся 6-12 сентабря 2015 г. в г. Геленджик.
Ответственность за аутентичность и точность цитат, имен, названий и иных сведений несут авторы публикуемых материалов. Материалы публикуются в авторской редакции.
Мероприятие проведено при финансовой поддержке Российского фонда фундаментальных исследований (грант № 15-07-20559-г). ...
Добавлено: 13 сентября 2015 г.
Бабенко М. А., Gawrychowski P., Kociumaka T. и др., , in : Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. : San Diego : SIAM, 2015. P. 572-591.
We present an improved wavelet tree construction algorithm and discuss its applications to a number of rank/select problems for integer keys and strings. Given a string of length n over an alphabet of size ω ≤ n, our method builds the wavelet tree in O(n log ω √log n) time, improving upon the state-of-the-art algorithm ...
Добавлено: 4 октября 2014 г.
Springer, 2019
Добавлено: 4 августа 2019 г.
Бабенко М. А., Колесниченко И. И., Smirnov I., Theory of Computing Systems 2019 Vol. 63 No. 4 P. 637-646
Heaps are well-studied fundamental data structures, having myriads of applications, both theoretical and practical. We consider the problem of designing a heap with an “optimal” extract-min operation. Assuming an arbitrary linear ordering of keys, a heap with n elements typically takes O(log n) time to extract the minimum. Extracting all elements faster is impossible as ...
Добавлено: 6 декабря 2019 г.
Рубцов А. А., Вялый М. Н., , in : Descriptional Complexity of Formal Systems: 23rd IFIP WG 1.02 International Conference, DCFS 2021, Virtual Event, September 5, 2021, Proceedings. : Springer, 2021. P. 150-162.
Добавлено: 2 февраля 2022 г.
Фомичев М. И., Ульянов М. В., Информационные технологии 2018 Т. 24 № 11 С. 698-704
Повышение временной эффективности программных реализаций метода ветвей и границ для асимметричной задачи коммивояжера может быть достигнуто как за счет выбора наиболее приемлемой структуры данных, обеспечивающей эффективные по времени операции с листьями поискового дерева решений, так и за счет использования дополнительной памяти для хранения усеченных матриц в листьях поискового дерева решений. Дополнительно могут быть предложены и ...
Добавлено: 26 января 2020 г.
Berlin, Heidelberg : Springer, 2017
The 12th issue of LNCS Transactions on Petri Nets and Other Models of Concurrency (ToPNoC) contains revised and extended versions of a selection of the best papers from the workshops held at the 37th International Conference on Application and Theory of Petri Nets and Concurrency (Petri Nets 2016, Toruń, Poland, 19–24 June 2016), and the ...
Добавлено: 27 сентября 2017 г.
Kucherov G., Nekrich Y., Gawrychowski P. и др., , in : Lecture Notes in Computer Science. Vol. 8214: Proceedings of the 20th Symposium on String Processing and Information Retrieval.: Berlin : Springer, 2013. P. 129-140.
We revisit two variants of the problem of computing minimal discriminating words studied in [5]. Given a pattern P and a threshold d, we want to report (i) all shortest extensions of P which occur in less than d documents, and (ii) all shortest extensions of P which occur only in d selected documents. For ...
Добавлено: 30 октября 2013 г.
Maxim Babenko, Gawrychowski P., Kociumaka T. и др., Theoretical Computer Science 2016 Vol. 638 P. 112-121
We consider the problems of computing the maximal and the minimal non-empty suffixes of substrings of a longer text of length . n. For the minimal suffix problem we show that for every . τ, . 1≤τ≤logn, there exists a linear-space data structure with . O(τ) query time and . O(nlogn/τ) preprocessing time. As a ...
Добавлено: 8 октября 2015 г.
Пономаренко А. А., В кн. : Труды 38-й конференции "Информационные технологии и системы - 2014". : Н. Новгород : ИППИ РАН, 2014. С. 194-200.
Классическим подходом к организации информации для последующего быстрого поиска является построение индекса. Однако этот подход имеет несколько недостатков. Индекс необходимо перестраивать и поддерживать в актуальном виде, что затруднительно в случае разрозненной информации, такой как текстовая информация в WEB. Эти недостатки являются следствием того, что индекс является реорганизованной копией индексируемой информации. В данной работе предлагается способ ...
Добавлено: 10 сентября 2014 г.
Kopelowitz T., Kucherov G., Nekrich Y. и др., Journal of Discrete Algorithms 2013
We study a new variant of the pattern matching problem called cross-document pattern matching, which is the problem of indexing a collection of documents to support an efficient search for a pattern in a selected document, where the pattern itself is a substring of another document. Several variants of this problem are considered, and efficient linear ...
Добавлено: 30 октября 2013 г.
Springer, 2019
Добавлено: 26 октября 2021 г.
Ulyanov M.V., Fomichev M.I., Business Informatics 2015 No. 4 (34) P. 38-46
Добавлено: 5 ноября 2016 г.