The Max-Shift Algorithm for Approximate String Matching

Costas S. Iliopoulos; Laurent Mouchard; Yoan J. Pinzon

doi:10.1007/3-540-44688-5_2

The Max-Shift Algorithm for Approximate String Matching

Costas S. Iliopoulos, Laurent Mouchard, Yoan J. Pinzon

Informatics

Research output: Chapter in Book/Report/Conference proceeding › Conference paper

12 Citations (Scopus)

Abstract

The approximate string matching problem is to find all locations which a pattern of length m matches a substring of a text of length n with at most k differences. The program agrep is a simple and practical bit-vector algorithm for this problem. We consider the following incremental version of the problem: given an appropriate encoding of a comparison between A and bB, can one compute the answer for A and B, and the answer for A and Bc with equal efficiency, where b and c are additional symbols? Here we present an elegant and very easy to implement bit-vector algorithm for answering these questions that requires only O(n[m/w]) time, where n is the length of A, m is the length of B and w is the number of bits in a machine word. We also present an O(nm[h/w]) algorithm for the fixed-length approximate string matching problem: given a text t, a pattern p and an integer h, compute the optimal alignment of all substrings of p of length h and a substring of t.

Original language	English
Title of host publication	Algorithm Engineering
Subtitle of host publication	5th International Workshop, WAE 2001 Århus, Denmark, August 28–31, 2001 Proceedings
Editors	G.S.Brodal , D.Frigioni , A.Marchetti-Spaccamela
Place of Publication	Berlin and New York
Publisher	Springer Berlin Heidelberg
Pages	13-25
Number of pages	13
Volume	N/A
Edition	N/A
ISBN (Print)	9783540425007
DOIs	https://doi.org/10.1007/3-540-44688-5_2
Publication status	Published - 2001
Event	WAE 2001: 5th International Workshop on Algorithm Engineering - Arhus, Denmark Duration: 28 Aug 2001 → 31 Aug 2001

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Berlin Heidelberg
Volume	2141
ISSN (Print)	0302-9743

Conference

Conference	WAE 2001: 5th International Workshop on Algorithm Engineering
Country/Territory	Denmark
City	Arhus
Period	28/08/2001 → 31/08/2001

Access to Document

10.1007/3-540-44688-5_2

Cite this

Iliopoulos, C. S., Mouchard, L., & Pinzon, Y. J. (2001). The Max-Shift Algorithm for Approximate String Matching. In G. S. B., D. F., & A. M.-S. (Eds.), Algorithm Engineering: 5th International Workshop, WAE 2001 Århus, Denmark, August 28–31, 2001 Proceedings (N/A ed., Vol. N/A, pp. 13-25). (Lecture Notes in Computer Science; Vol. 2141). Springer Berlin Heidelberg. https://doi.org/10.1007/3-540-44688-5_2

Iliopoulos, Costas S. ; Mouchard, Laurent ; Pinzon, Yoan J. / The Max-Shift Algorithm for Approximate String Matching. Algorithm Engineering: 5th International Workshop, WAE 2001 Århus, Denmark, August 28–31, 2001 Proceedings. editor / G.S.Brodal ; D.Frigioni ; A.Marchetti-Spaccamela. Vol. N/A N/A. ed. Berlin and New York : Springer Berlin Heidelberg, 2001. pp. 13-25 (Lecture Notes in Computer Science).

@inbook{091879cab6a64e45ba3939470d801beb,

title = "The Max-Shift Algorithm for Approximate String Matching",

abstract = "The approximate string matching problem is to find all locations which a pattern of length m matches a substring of a text of length n with at most k differences. The program agrep is a simple and practical bit-vector algorithm for this problem. We consider the following incremental version of the problem: given an appropriate encoding of a comparison between A and bB, can one compute the answer for A and B, and the answer for A and Bc with equal efficiency, where b and c are additional symbols? Here we present an elegant and very easy to implement bit-vector algorithm for answering these questions that requires only O(n[m/w]) time, where n is the length of A, m is the length of B and w is the number of bits in a machine word. We also present an O(nm[h/w]) algorithm for the fixed-length approximate string matching problem: given a text t, a pattern p and an integer h, compute the optimal alignment of all substrings of p of length h and a substring of t. ",

author = "Iliopoulos, {Costas S.} and Laurent Mouchard and Pinzon, {Yoan J.}",

year = "2001",

doi = "10.1007/3-540-44688-5_2",

language = "English",

isbn = "9783540425007",

volume = "N/A",

series = "Lecture Notes in Computer Science",

publisher = "Springer Berlin Heidelberg",

pages = "13--25",

editor = "G.S.Brodal and D.Frigioni and A.Marchetti-Spaccamela",

booktitle = "Algorithm Engineering",

edition = "N/A",

note = "WAE 2001: 5th International Workshop on Algorithm Engineering ; Conference date: 28-08-2001 Through 31-08-2001",

}

Iliopoulos, CS , Mouchard, L & Pinzon, YJ 2001, The Max-Shift Algorithm for Approximate String Matching. in GSB, DF & AM-S (eds), Algorithm Engineering: 5th International Workshop, WAE 2001 Århus, Denmark, August 28–31, 2001 Proceedings. N/A edn, vol. N/A, Lecture Notes in Computer Science, vol. 2141, Springer Berlin Heidelberg, Berlin and New York, pp. 13-25, WAE 2001: 5th International Workshop on Algorithm Engineering, Arhus, Denmark, 28/08/2001. https://doi.org/10.1007/3-540-44688-5_2

The Max-Shift Algorithm for Approximate String Matching. / Iliopoulos, Costas S.; Mouchard, Laurent ; Pinzon, Yoan J.
Algorithm Engineering: 5th International Workshop, WAE 2001 Århus, Denmark, August 28–31, 2001 Proceedings. ed. / G.S.Brodal; D.Frigioni; A.Marchetti-Spaccamela. Vol. N/A N/A. ed. Berlin and New York: Springer Berlin Heidelberg, 2001. p. 13-25 (Lecture Notes in Computer Science; Vol. 2141).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper

TY - CHAP

T1 - The Max-Shift Algorithm for Approximate String Matching

AU - Iliopoulos, Costas S.

AU - Mouchard, Laurent

AU - Pinzon, Yoan J.

PY - 2001

Y1 - 2001

N2 - The approximate string matching problem is to find all locations which a pattern of length m matches a substring of a text of length n with at most k differences. The program agrep is a simple and practical bit-vector algorithm for this problem. We consider the following incremental version of the problem: given an appropriate encoding of a comparison between A and bB, can one compute the answer for A and B, and the answer for A and Bc with equal efficiency, where b and c are additional symbols? Here we present an elegant and very easy to implement bit-vector algorithm for answering these questions that requires only O(n[m/w]) time, where n is the length of A, m is the length of B and w is the number of bits in a machine word. We also present an O(nm[h/w]) algorithm for the fixed-length approximate string matching problem: given a text t, a pattern p and an integer h, compute the optimal alignment of all substrings of p of length h and a substring of t.

AB - The approximate string matching problem is to find all locations which a pattern of length m matches a substring of a text of length n with at most k differences. The program agrep is a simple and practical bit-vector algorithm for this problem. We consider the following incremental version of the problem: given an appropriate encoding of a comparison between A and bB, can one compute the answer for A and B, and the answer for A and Bc with equal efficiency, where b and c are additional symbols? Here we present an elegant and very easy to implement bit-vector algorithm for answering these questions that requires only O(n[m/w]) time, where n is the length of A, m is the length of B and w is the number of bits in a machine word. We also present an O(nm[h/w]) algorithm for the fixed-length approximate string matching problem: given a text t, a pattern p and an integer h, compute the optimal alignment of all substrings of p of length h and a substring of t.

UR - http://www.scopus.com/inward/record.url?scp=78650726931&partnerID=8YFLogxK

U2 - 10.1007/3-540-44688-5_2

DO - 10.1007/3-540-44688-5_2

M3 - Conference paper

SN - 9783540425007

VL - N/A

T3 - Lecture Notes in Computer Science

SP - 13

EP - 25

BT - Algorithm Engineering

A2 - null, G.S.Brodal

A2 - null, D.Frigioni

A2 - null, A.Marchetti-Spaccamela

PB - Springer Berlin Heidelberg

CY - Berlin and New York

T2 - WAE 2001: 5th International Workshop on Algorithm Engineering

Y2 - 28 August 2001 through 31 August 2001

ER -

Iliopoulos CS , Mouchard L , Pinzon YJ. The Max-Shift Algorithm for Approximate String Matching. In GSB, DF, AMS, editors, Algorithm Engineering: 5th International Workshop, WAE 2001 Århus, Denmark, August 28–31, 2001 Proceedings. N/A ed. Vol. N/A. Berlin and New York: Springer Berlin Heidelberg. 2001. p. 13-25. (Lecture Notes in Computer Science). doi: 10.1007/3-540-44688-5_2

The Max-Shift Algorithm for Approximate String Matching

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this