The swap matching problem consists in finding all occurrences of a pattern x of length m in a text y of length n, allowing for disjoint local swaps of characters in the pattern. In 2003, Amir et al. solved the problem in (nlogmlogσ) worst-case time complexity, where σ is the size of the alphabet. In recent years, much research has focused on practical solutions and efficient algorithms have been devised by means of the bit-parallel simulation of non-deterministic automata. In this paper, we present a new efficient algorithm for the swap matching problem based on character comparison and structured as a generalization of the Skip-Search algorithm for the exact string matching problem. Although our solution has a quadratic worst-case time complexity, it shows a sub-linear behaviour on average. According to experimental results, our algorithm obtains in most practical cases the best running times, when compared against the most effective solutions. The gain in speed-up, in terms of running times, is up to 48%. This makes the new algorithm one of the most efficient solutions in practical cases.
An Efficient Skip-Search Approach to Swap Matching
Faro, Simone
;
2018-01-01
Abstract
The swap matching problem consists in finding all occurrences of a pattern x of length m in a text y of length n, allowing for disjoint local swaps of characters in the pattern. In 2003, Amir et al. solved the problem in (nlogmlogσ) worst-case time complexity, where σ is the size of the alphabet. In recent years, much research has focused on practical solutions and efficient algorithms have been devised by means of the bit-parallel simulation of non-deterministic automata. In this paper, we present a new efficient algorithm for the swap matching problem based on character comparison and structured as a generalization of the Skip-Search algorithm for the exact string matching problem. Although our solution has a quadratic worst-case time complexity, it shows a sub-linear behaviour on average. According to experimental results, our algorithm obtains in most practical cases the best running times, when compared against the most effective solutions. The gain in speed-up, in terms of running times, is up to 48%. This makes the new algorithm one of the most efficient solutions in practical cases.File | Dimensione | Formato | |
---|---|---|---|
FaroPavone - The Computer Journal copia.pdf
solo gestori archivio
Tipologia:
Versione Editoriale (PDF)
Licenza:
Creative commons
Dimensione
402.71 kB
Formato
Adobe PDF
|
402.71 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.