Fast parameterized matching with q-grams

被引：8
|
作者：
Salmela, Leena [1 ]
Tarhio, Jorma [1 ]
机构：
[1] Aalto Univ, Dept Comp Sci & Engn, Helsinki, Finland
来源：
JOURNAL OF DISCRETE ALGORITHMS | 2008年 / 6卷 / 03期
基金：
芬兰科学院;
关键词：
String matching; 2-dimensional string matching; Parameterized matching;
D O I：
10.1016/j.jda.2007.11.001
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
Two strings parameterize match if there is a bijection defined on the alphabet that transforms the first string character by character into the second string. The problem of finding all parameterized matches of a pattern in a text has been studied in both one and two dimensions but the research has been centered on developing algorithms with good worst-case performance. We present algorithms that solve this problem in sublinear time on average for moderately repetitive patterns. (C) 2007 Elsevier B.V. All rights reserved.
引用
收藏
页码：408 / 419
页数：12
相关论文
共 50 条
  • [1] MAINTAINING SOFTWARE THROUGH BIT-PARALLELISM AND HASHING THE PARAMETERIZED Q-GRAMS
    Prasad, Rajesh
    Agarwal, Suneeta
    Misra, Sanjay
    Sharma, Anuj Kumar
    Singh, Alok
    TEHNICKI VJESNIK-TECHNICAL GAZETTE, 2012, 19 (02): : 243 - 247
  • [2] APPROXIMATE STRING-MATCHING WITH Q-GRAMS AND MAXIMAL MATCHES
    UKKONEN, E
    THEORETICAL COMPUTER SCIENCE, 1992, 92 (01) : 191 - 211
  • [3] Indexing text with approximate q-grams
    Navarro, Gonzalo
    Sutinen, Erkki
    Tarhio, Jorma
    JOURNAL OF DISCRETE ALGORITHMS, 2005, 3 (2-4) : 157 - 175
  • [4] Indexing text with approximate q-grams
    Navarro, G
    Sutinen, E
    Tanninen, J
    Tarhio, J
    COMBINATORIAL PATTERN MATCHING, 2000, 1848 : 350 - 363
  • [5] Better filtering with gapped q-grams
    Burkhardt, S
    Kärkkäinen, J
    FUNDAMENTA INFORMATICAE, 2003, 56 (1-2) : 51 - 70
  • [6] Circular Sequence Comparison with q-grams
    Grossi, Roberto
    Iliopoulos, Costas S.
    Mercas, Robert
    Pisanti, Nadia
    Pissis, Solon P.
    Retha, Ahmad
    Vayani, Fatima
    ALGORITHMS IN BIOINFORMATICS (WABI 2015), 2015, 9289 : 203 - 216
  • [7] Lempel-Ziv index for q-grams
    Karkkainen, J
    Sutinen, E
    ALGORITHMICA, 1998, 21 (01) : 137 - 154
  • [8] Indexing DNA sequences using q-grams
    Cao, X
    Li, SC
    Tung, AKH
    DATABASE SYSTEMS FOR ADVANCED APPLICATIONS, PROCEEDINGS, 2005, 3453 : 4 - 16
  • [9] Regular Expression Filtering on Multiple q-Grams
    Shin, Seon-Ho
    Kim, HyunBong
    Yoon, MyungKeun
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2018, E101D (01) : 253 - 256
  • [10] Tuning bg multi-pattern string matching algorithm with unrolling q-grams and hash
    Yang, P.
    Fan, H.
    Huang, Qi
    Liu, Li
    Computer Modelling and New Technologies, 2013, 17 (04): : 58 - 65
12345