Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

 
 
DownloadE-Mail
  Computing the threshold for q-gram filters

Kärkkäinen, J. (2002). Computing the threshold for q-gram filters. In Algorithm theory, SWAT 2002: 8th Scandinavian Workshop on Algorithm Theory (pp. 348-357). Berlin, Germany: Springer.

Item is

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Kärkkäinen, Juha1, Autor           
Penttonen, Martti, Herausgeber
Meineche Schmidt, Erik, Herausgeber
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: A popular and much studied class of filters for approximate string matching is based on finding common $q$-grams, substrings of length $q$, between the pattern and the text. A variation of the basic idea uses \emph{gapped} $q$-grams and has been recently shown to provide significant improvements in practice. A major difficulty with gapped $q$-gram filters is the computation of the so-called \emph{threshold} which defines the filter criterium. We describe the first general method for computing the threshold for $q$-gram filters. The method is based on a carefully chosen precise statement of the problem which is then transformed into a constrained shortest path problem. In its generic form the method leaves certain parts open but is applicable to a large variety of $q$-gram filters and may be extensible even to other classes of filters. We also give a full algorithm for a specific subclass. For this subclass, the algorithm has been implemented and used succesfully in an experimental comparison.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2003-08-272002
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 202062
Anderer: Local-ID: C1256428004B93B8-BDE5926620208DA2C1256CE5006C7B5E-Karkkainen2002
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: SWAT 2002
Veranstaltungsort: Turku, Finland
Start-/Enddatum: 2002-07-03 - 2002-07-05

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Algorithm theory, SWAT 2002 : 8th Scandinavian Workshop on Algorithm Theory
Genre der Quelle: Konferenzband
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: Berlin, Germany : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 348 - 357 Identifikator: ISBN: 3-540-43866-1

Quelle 2

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