Automatically assigned DDC number: 0051

Manually assigned DDC number: 0064

Number of references: 4

Title: A Partial Deterministic Automaton for Approximate String Matching

Author:

Subject: Gonzalo Navarro A Partial Deterministic Automaton for Approximate String Matching

Description: . One of the simplest approaches to approximate string matching is to consider the associated non-deterministic finite automaton and make it deterministic. Besides automaton generation, the search time is O(n) in the worst case, where n is the text size. This solution is mentioned in the classical literature but has not been further pursued, due to the large number of automaton states that may be generated. We study the idea of generating the deterministic automaton on the fly. That is, we only generate the states that are actually reached when the text is traversed. We show that this limits drastically the number of states actually generated. Moreover, the algorithm is competitive, being the fastest one for intermediate error ratios and pattern lengths. 1 Introduction Approximate string matching is one of the main problems in classical string algorithms, with applications to text searching, computational biology, pattern recognition, etc. The problem is defined as follows: given a t...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1997-09-02

Pubyear: 1997

Format: ps

Identifier: http://citeseer.ist.psu.edu/148605.html

Source: ftp://ftp.dcc.uchile.cl/pub/users/gnavarro/wsp97.2.ps.gz

Language: en

Relation:

Relation:

Relation:

Relation:

Rights: unrestricted

Graph

<?xml   version="1.0"   encoding="UTF-8"?>

<references_metadata>

      <rec   ID="/253812.html"   Type="inproceedings"   CiteSeer_Book="ISAAC   5th   International   Symposium   on   Algorithms   and   Computation   formerly   SIGAL   International   Symposium   on   Algorithms   Organized   by   Special   Interest   Group   on   Algorithms   SIGAL   of   the   Information   Processing   Society   of   Japan   IPSJ   and   the   Technical   Group   on   Theoretical   Foundation   of   Computing   of   the   Institute   of   Electronics   Information   and   Communication   Engineers   IEICE"   CiteSeer_Volume=""   Title="Approximate   Pattern   Matching   with   Samples,">

            <identifier   Org="ISBN:3540297405"   Paper_ID="/253812.html"   Extracted="3540297405"   DDC="005.52"   Normalized_DDC="00552"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:3540422714"   Paper_ID="/253812.html"   Extracted="3540422714"   DDC="006.4015116"   Normalized_DDC="0064015116"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:3540438661"   Paper_ID="/253812.html"   Extracted="3540438661"   DDC="511.8"   Normalized_DDC="5118"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:3540583254"   Paper_ID="/253812.html"   Extracted="3540583254"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:3540603131"   Paper_ID="/253812.html"   Extracted="3540603131"   DDC="004/.01/5118"   Normalized_DDC="004015118"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:3540612580"   Paper_ID="/253812.html"   Extracted="3540612580"   DDC="006.4/01/5116"   Normalized_DDC="0064015116"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:3540632204"   Paper_ID="/253812.html"   Extracted="3540632204"   DDC="006.4015116"   Normalized_DDC="0064015116"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:3540633073"   Paper_ID="/253812.html"   Extracted="3540633073"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.1111111111111111"   />

            <identifier   Org="ISBN:354064380X"   Paper_ID="/253812.html"   Extracted="354064380X"   DDC="004/.01/9"   Normalized_DDC="004019"   Normalized_Weight="0.1111111111111111"   />

      </rec>

      <rec   ID="/579273.html"   Type="article"   CiteSeer_Book="Software      Practice   and   Experience"   CiteSeer_Volume="24"   Title="Approximate   String   Matching   using   Within-word   Parallelism,">

            <identifier   Org="ISBN:0201398397"   Paper_ID="/579273.html"   Extracted="0201398397"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:3540201777"   Paper_ID="/579273.html"   Extracted="3540201777"   DDC="005.74"   Normalized_DDC="00574"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:3540259201"   Paper_ID="/579273.html"   Extracted="3540259201"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:3540425004"   Paper_ID="/579273.html"   Extracted="3540425004"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:3540612580"   Paper_ID="/579273.html"   Extracted="3540612580"   DDC="006.4/01/5116"   Normalized_DDC="0064015116"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:3540633073"   Paper_ID="/579273.html"   Extracted="3540633073"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.16666666666666666"   />

      </rec>

      <rec   ID="/174195.html"   Type="inproceedings"   CiteSeer_Book="Proceedings   USENIX   Winter   1992   Technical   Conference"   CiteSeer_Volume=""   Title="Agrep   --   a   fast   approximate   pattern-matching   tool,">

            <identifier   Org="ISBN:0201309874"   Paper_ID="/174195.html"   Extracted="0201309874"   DDC="004.019"   Normalized_DDC="004019"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:0387560246"   Paper_ID="/174195.html"   Extracted="0387560246"   DDC="005.73/01/5116"   Normalized_DDC="00573015116"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:0818681624"   Paper_ID="/174195.html"   Extracted="0818681624"   DDC="005.3"   Normalized_DDC="0053"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:0818689676"   Paper_ID="/174195.html"   Extracted="0818689676"   DDC="005.1/6"   Normalized_DDC="00516"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:0849326494"   Paper_ID="/174195.html"   Extracted="0849326494"   DDC="511.3"   Normalized_DDC="5113"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:089791970X"   Paper_ID="/174195.html"   Extracted="089791970X"   DDC="005.74"   Normalized_DDC="00574"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:1581133537"   Paper_ID="/174195.html"   Extracted="1581133537"   />

            <identifier   Org="ISBN:3540296395"   Paper_ID="/174195.html"   Extracted="3540296395"   DDC="005.2/75"   Normalized_DDC="005275"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540425004"   Paper_ID="/174195.html"   Extracted="3540425004"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540438629"   Paper_ID="/174195.html"   Extracted="3540438629"   DDC="006.4015116"   Normalized_DDC="0064015116"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540612580"   Paper_ID="/174195.html"   Extracted="3540612580"   DDC="006.4/01/5116"   Normalized_DDC="0064015116"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540632204"   Paper_ID="/174195.html"   Extracted="3540632204"   DDC="006.4015116"   Normalized_DDC="0064015116"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540642757"   Paper_ID="/174195.html"   Extracted="3540642757"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:354064380X"   Paper_ID="/174195.html"   Extracted="354064380X"   DDC="004/.01/9"   Normalized_DDC="004019"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540664270"   Paper_ID="/174195.html"   Extracted="3540664270"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540739211"   Paper_ID="/174195.html"   Extracted="3540739211"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3642003818"   Paper_ID="/174195.html"   Extracted="3642003818"   />

      </rec>

      <rec   ID="/350080.html"   Type="article"   CiteSeer_Book="Algorithmica"   CiteSeer_Volume="15"   Title="A   Subquadratic   Algorithm   for   Approximate   Limited   Expression   Matching,">

            <identifier   Org="ISBN:0201398397"   Paper_ID="/350080.html"   Extracted="0201398397"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.125"   />

            <identifier   Org="ISBN:0306447126"   Paper_ID="/350080.html"   Extracted="0306447126"   DDC="574.87/3282/0151"   Normalized_DDC="5748732820151"   Normalized_Weight="0.125"   />

            <identifier   Org="ISBN:0521813077"   Paper_ID="/350080.html"   Extracted="0521813077"   DDC="005.74"   Normalized_DDC="00574"   Normalized_Weight="0.125"   />

            <identifier   Org="ISBN:1604561866"   Paper_ID="/350080.html"   Extracted="1604561866"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.125"   />

            <identifier   Org="ISBN:3540425004"   Paper_ID="/350080.html"   Extracted="3540425004"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.125"   />

            <identifier   Org="ISBN:3540632204"   Paper_ID="/350080.html"   Extracted="3540632204"   DDC="006.4015116"   Normalized_DDC="0064015116"   Normalized_Weight="0.125"   />

            <identifier   Org="ISBN:3540647392"   Paper_ID="/350080.html"   Extracted="3540647392"   DDC="006.4015116"   Normalized_DDC="0064015116"   Normalized_Weight="0.125"   />

            <identifier   Org="ISBN:3540755292"   Paper_ID="/350080.html"   Extracted="3540755292"   DDC="005.52"   Normalized_DDC="00552"   Normalized_Weight="0.125"   />

      </rec>

      <rec   ID="SELF"   Type="SELF"   CiteSeer_Book="SELF"   CiteSeer_Volume="SELF"   Title="A   Partial   Deterministic   Automaton   for   Approximate   String   Matching">

            <identifier   Org="ISBN:1604561866"   Paper_ID="SELF"   Extracted="1604561866"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.3333333333333333"   />

            <identifier   Org="ISBN:3540008837"   Paper_ID="SELF"   Extracted="3540008837"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.3333333333333333"   />

            <identifier   Org="ISBN:3540647392"   Paper_ID="SELF"   Extracted="3540647392"   DDC="006.4015116"   Normalized_DDC="0064015116"   Normalized_Weight="0.3333333333333333"   />

      </rec>

</references_metadata>