he Pattern Matching problem with Swaps consists in finding all occurrences of a pattern P in a text T, when disjoint local swaps in the pattern are allowed. In the Approximate Pattern Matching problem with Swaps one seeks, for every text location with a swapped match of P, the number of swaps necessary to obtain a match at the location. In this paper we devise two general algorithms for both Standard and Approximate Pattern Matching with Swaps, named CROSS-SAMPLING and BACKWARD-CROSS-SAMPLING, with a O(nm) and O(nm(2)) worst-case time complexity, respectively. Then we provide efficient implementations of them, based on bit-parallelism, which achieve O(n) and O(nm) worst-case time complexity, with patterns v-hose length is comparable to the word-size of the target machine. From an extensive comparison with. some of the most Live algorithms for the matching problem, it turns out that our algorithms a) very flexible and achieve very good results in practice.
Pattern matching with swaps in practice
CANTONE, Domenico;FARO, SIMONE;
2012-01-01
Abstract
he Pattern Matching problem with Swaps consists in finding all occurrences of a pattern P in a text T, when disjoint local swaps in the pattern are allowed. In the Approximate Pattern Matching problem with Swaps one seeks, for every text location with a swapped match of P, the number of swaps necessary to obtain a match at the location. In this paper we devise two general algorithms for both Standard and Approximate Pattern Matching with Swaps, named CROSS-SAMPLING and BACKWARD-CROSS-SAMPLING, with a O(nm) and O(nm(2)) worst-case time complexity, respectively. Then we provide efficient implementations of them, based on bit-parallelism, which achieve O(n) and O(nm) worst-case time complexity, with patterns v-hose length is comparable to the word-size of the target machine. From an extensive comparison with. some of the most Live algorithms for the matching problem, it turns out that our algorithms a) very flexible and achieve very good results in practice.File | Dimensione | Formato | |
---|---|---|---|
2012 CampanelliCantoneFaroGiaquinta IJFCS.pdf
solo gestori archivio
Tipologia:
Versione Editoriale (PDF)
Dimensione
324.76 kB
Formato
Adobe PDF
|
324.76 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.