Bit-parallel (δ, γ)-matching and suffix automata

摘要

(δ, γ)-matching is a string matching problem with applications to music retrieval. The goal is, given a pattern P_(1...m) and a text T_(1...n) on an alphabet of integers, find the occurrences P′ of the pattern in the text such that (ⅰ) any1 ≤ i ≤ m, |P_i-P′_i| ≤ δ, and (ⅱ)∑_1≤ i ≤ m |P_i-P′_i| ≤ γ. The problem makes sense for δ≤ γ ≤ δm. Several techniques for (δ, γ)-matching have been proposed, based on bit-parallelism or on skipping characters. We first present an O(mn log(γ)/w) worst-case time and O(n) average-case time bit-parallel algorithm (being w the number of bits in the computer word). It improves the previous O(mn log (δm)/w) worst-case time algorithm of the same type. Second, we combine our bit-parallel algorithm with suffix automata to obtain the first algorithm that skips characters using both δ and γ. This algorithm examines less characters than any previous approach, as the others do just δ-matching and check the γ-condition on the candidates. We implemented our algorithms and drew experimental results on real music, showing that our algorithms are superior to current alternatives with high values of δ.