wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

approximate_pattern_matching (635B)

      1 # Approximate pattern matching
      2 
      3 - find all occurrences of a pattern P in text T up to k modifications ([string_distance])
      4 - only report the end of matches to avoid quadratic output
      5 
      6 can be for [hamming_distance] or for [edit_distance] (cf [navarro2001guided])
      7 
      8 variant: [approximate_pattern_matching_streaming]
      9 
     10 special cases when the [string_distance] is not too big (bounded by k):
     11 - [k_mismatch_pattern_matching] for [hamming_distance]
     12 - [k_edit_pattern_matching] for [edit_distance]
     13 
     14 [academic_papers]:
     15 
     16 - [hazay2007approximate]
     17 - [bathie2024longest]
     18 
     19 Up: [pattern_matching], [approximation]
     20 
     21 Aliases: pattern matching approximate