Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
On the Hardness of Optimal Vertex Relabeling and Restricted Vertex Relabeling Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Alphabet-Dependent String Searching with Wexponential Search Trees

verfasst von : Johannes Fischer, Paweł Gawrychowski

Erschienen in: Combinatorial Pattern Matching

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We consider finding a pattern of length \(m\) in a compacted (linear-size) trie storing strings over an alphabet of size \(\sigma \). In static tries, we achieve \(O(m+\lg \lg \sigma )\) deterministic time, whereas in dynamic tries we achieve \(O(m+\frac{\lg ^{2}\lg \sigma }{\lg \lg \lg \sigma })\) deterministic time per query or update. One particular application of the above bounds (static and dynamic) are suffix trees, where we also show how to pre- or append letters in \(O(\lg \lg n + \frac{\lg ^{2}\lg \sigma }{\lg \lg \lg \sigma })\) time. Our main technical contribution is a weighted variant of exponential search trees, which might be of independent interest.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Range Minimum Query Indexes in Higher Dimensions
Nächstes Kapitel Lempel Ziv Computation in Small Space (LZ-CISS)
Literatur
1.
Amir, A., Franceschini, G., Grossi, R., Kopelowitz, T., Lewenstein, M., Lewenstein, N.: Managing unbounded-length keys in comparison-driven data structures with applications to online indexing. SIAM J. Comput. 43(4), 1396–1416 (2014)MATHMathSciNetCrossRef
2.
Andersson, A., Thorup, M.: Dynamic ordered sets with exponential search trees. J. ACM 53(3) (2007). Article No. 13
3.
Beame, P., Fich, F.E.: Optimal bounds for the predecessor problem and related problems. J. Comput. Syst. Sci. 65(1), 38–72 (2002)MATHMathSciNetCrossRef
4.
Bender, M.A., Cole, R., Raman, R.: Exponential structures for efficient cache-oblivious algorithms. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 195–207. Springer, Heidelberg (2002) CrossRef
5.
Breslauer, D., Italiano, G.F.: Near real-time suffix tree construction via the fringe marked ancestor problem. J. Discrete Algorithms 18, 32–48 (2013)MATHMathSciNetCrossRef
6.
Cole, R., Kopelowitz, T., Lewenstein, M.: Suffix trays and suffix trists: structures for faster text indexing. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 358–369. Springer, Heidelberg (2006) CrossRef
7.
8.
Fredman, M.L., Komlós, J., Szemerédi, E.: Storing a sparse table with \({O}(1)\) worst case access time. J. ACM 31(3), 538–544 (1984)MATHCrossRef
9.
Kopelowitz, T.: On-line indexing for general alphabets via predecessor queries on subsets of an ordered list. In: Proceedings of the FOCS, pp. 283–292. IEEE Computer Society (2012)
10.
Kucherov, G., Nekrich, Y.: Full-fledged real-time indexing for constant size alphabets. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 650–660. Springer, Heidelberg (2013) CrossRef
11.
12.
13.
14.
Ružić, M.: Constructing efficient dictionaries in close to sorting time. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 84–95. Springer, Heidelberg (2008) CrossRef
15.
Weiner, P.: Linear pattern matching algorithms. In: Proceedings of the Annual Symposium on Switching and Automata Theory, pp. 1–11. IEEE Computer Society (1973)
Metadaten
Titel
Alphabet-Dependent String Searching with Wexponential Search Trees
verfasst von
Johannes Fischer
Paweł Gawrychowski
Copyright-Jahr
2015
Buch
Combinatorial Pattern Matching

Print ISBN: 978-3-319-19928-3

Electronic ISBN: 978-3-319-19929-0

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-19929-0_14