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
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Detecting Anomalous Ratings Using Matrix Factorization for Recommender Systems Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Efficient Approximate Substring Matching in Compressed String

verfasst von : Yutong Han, Bin Wang, Xiaochun Yang

Erschienen in: Web-Age Information Management

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

The idea of LZ77 self-index has been proposed for repetitive text in compressed forms. Existing methods of approximate string matching based on LZ77 focus on space efficiency. We focus on how to efficiently search similar strings in text without decompressing the whole text. We propose RS-search algorithm to merge all the occurrences of substring efficiently to narrow down the potential region and design novel filterings to reduce the scale of candidates. The experiments show that our algorithm achieves outstanding performance and an interesting time-space trade-off in approximate matching for compressed string.

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 Diversification of Keyword Query Result Patterns
Nächstes Kapitel Top-K Similarity Search for Query-By-Humming
Fußnoten
1
\(rank_{b}(B,\; i) \) is the number of occurrences of bit b in \(B_{1,\;i}\).
 
Literatur
1.
Qin, J., Wang, W., Xiao, C., Lu, Y., Lin, X., Wang, H.: Asymmetric signature schemes for efficient exact edit similarity query processing. ACM Trans. Database Syst. (TODS) 38(3), 16 (2013)MathSciNetCrossRefMATH
2.
Navarro, G., Baeza-Yates, R.: A hybrid indexing method for approximate string matching. J. Discrete Algorithms 1(1), 205–239 (2000)MathSciNet
3.
Deng, D., Li, G., Feng, J.: A pivotal prefix based filtering algorithm for string similarity search. In: ACM Sigmod International Conference on Management of Data, pp. 673–684 (2014)
4.
Li, C., Lu, J., Lu, Y.: Efficient merging and filtering algorithms for approximate string searches. In: IEEE 24th International Conference on Data Engineering, ICDE 2008, pp. 257–266 (2008)
5.
Wandelt, S., Starlinger, J., Bux, M., Leser, U.: RCSI: scalable similarity search in thousand(s) of genomes. Proc. VLDB Endow. 6(13), 1534–1545 (2013)CrossRef
6.
Wandelt, S., Leser, U.: MRCSI: compressing and searching string collections with multiple references. PVLDB 8(5), 461–472 (2015)
7.
Yang, X., Wang, B., Li, C., Wang, J.: Efficient direct search on compressed genomic data. In: 2013 IEEE 29th International Conference on Data Engineering (ICDE), pp. 961–972 (2013)
8.
Kreft, S., Navarro, G.: Self-indexing based on LZ77. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol. 6661, pp. 41–54. Springer, Heidelberg (2011)CrossRef
9.
Gagie, T., Gawrychowski, P., Puglisi, S.J.: Approximate pattern matching in LZ77-compressed texts. J. Discrete Algorithms 32, 64–68 (2014)MathSciNetCrossRefMATH
10.
Russo, L.M.S., Navarro, G., Oliveira, A.L., Morales, P.: Approximate string matching with compressed indexes. Algorithms 2(3), 1105–1136 (2009)MathSciNetCrossRef
11.
Bille, P., Fagerberg, R., Li Gørtz, I.: Improved approximate string matching and regular expression matching on Ziv-Lempel compressed texts. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol. 4580, pp. 52–62. Springer, Heidelberg (2007)CrossRef
12.
Navarro, G., Baeza-Yates, R., Sutinen, E., Tarhio, J.: Indexing methods for approximate string matching. IEEE Data Eng. Bull. 24(85), 19–27 (2001)
13.
Russo, L.M.S., Navarro, G., Oliveira, A.L.: Approximate string matching with Lempel-Ziv compressed indexes. In: Ziviani, N., Baeza-Yates, R. (eds.) SPIRE 2007. LNCS, vol. 4726, pp. 264–275. Springer, Heidelberg (2007)CrossRef
14.
Levenstein, V.: Binary codes capable of correcting spurious insertions and deletions of ones. Probl. Inf. Transm. 1(1), 8–17 (1965)MathSciNet
15.
Schneeberger, K., Hagmann, J., Ossowski, S., Warthmann, N., Gesing, S., Kohlbacher, O., Weigel, D.: Simultaneous alignment of short reads against multiple genomes. Genome Biol. 10(9), R98 (2009)CrossRef
Metadaten
Titel
Efficient Approximate Substring Matching in Compressed String
verfasst von
Yutong Han
Bin Wang
Xiaochun Yang
Copyright-Jahr
2016
Buch
Web-Age Information Management

Print ISBN: 978-3-319-39957-7

Electronic ISBN: 978-3-319-39958-4

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-39958-4_15

Neuer Inhalt

    Bildnachweise