Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Better Filtering with Gapped q-Grams

Burkhardt, S., & Kärkkäinen, J. (2001). Better Filtering with Gapped q-Grams. In A. Amir, & G. Landau (Eds.), Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching (pp. 73-85). Berlin, Germany: Springer.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3179-D Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-317B-9
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Burkhardt, Stefan1, Autor           
Kärkkäinen, Juha1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: The q-gram filter is a popular filtering method for approximate string matching. It compares substrings of length q (the q-grams) in the pattern and the text to identify the text areas that might contain a match. A generalization of the method is to use gapped q-grams, subsets of q characters in some fixed non-contiguous shape, instead of contiguous substrings. Although mentioned a few times in the literature, this generalization has never been studied in any depth. In ths paper, we report the first results from a study on gapped q-grams. We show that gapped q-grams can provide orders of magnitude faster and/or more efficient filtering than contiguous q-grams. The performance, however, depends on the shape of the q-grams. The best shaoes are rare and often posess no apparen regularity. We show how to recognize good shapes and demonstrate with experiments their advantage over both contiguous and average shapes. We concentrate here on the k mismatches problem, but also outline an approach for extending the results to the more common k differences problem.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2010-03-022001
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 518175
URI: http://www.mpi-sb.mpg.de/~stburk/gapped-q.ps
Anderer: Local-ID: C1256428004B93B8-5165C4C93C02B85DC1256A8F00420FEE-Burkhardt2001
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Untitled Event
Veranstaltungsort: Jerusalem, Israel
Start-/Enddatum: 2001

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching
Genre der Quelle: Konferenzband
 Urheber:
Amir, Amihood, Herausgeber
Landau, Gadi, Herausgeber
Affiliations:
-
Ort, Verlag, Ausgabe: Berlin, Germany : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 73 - 85 Identifikator: ISBN: 3-540-42271-4

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 2089 Artikelnummer: - Start- / Endseite: - Identifikator: -