Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2007-12-25
2007-12-25
Rones, Charles (Department: 2164)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
11119509
ABSTRACT:
This invention related to a method for computing the minimum edit distance, measured as the number of insertions plus the number of deletions, between two sequences of data, which runs in an amount of time that is nearly proportional to the size of the input data under many circumstances. Utilizing the A* (or A-star) search, the invention searches for the answer using a novel counting heuristic that gives a lower bound on the minimum edit distance for any given subproblem. In addition, regions over which the heuristic matches the maximum value of the answer are optimized by eliminating the search over redundant paths. The invention can also be used to produce the edit script. The invention can be modified for other types of comparison and pattern recognition.
REFERENCES:
patent: 5459739 (1995-10-01), Handley et al.
patent: 6119120 (2000-09-01), Miller
patent: 6349296 (2002-02-01), Broder et al.
patent: 6446068 (2002-09-01), Kortge
patent: 2003/0195890 (2003-10-01), Oommen
Davi De Castro et al., Automatic Web News Extraction Using Tree Edit Distrance, In Proc. 13th Intl. Conf. on the World Wide Web, 2004, pp. 502-511, New York.
Saurabh Mittal, Implementation of K-shortest Path Dijkstra Algorithm used in All-optical Data Communication Networks, SIE 546 project, Spring 2004, Arizona.
T. Batu et al., A Sublinear Algorithm for Weakly Approximating Edit Distance, Proc. 35th Annual ACM Symposium on Theory of Computing, 2003, p. 359.
Richard Sproat, Ling 306, Introductio nto Computational Linguistics, Sep. 2003, Univ. of IL Urbana-Champaign http://www.staff.uluc.edu/˜rws/Courses/L306, all pages.
Serge Dulucq et al., Analysis of Tree Edit Distance Algorithms, Proc. 14th Annual Symp. on Comb. Pattern Matching ,Jun. 2003, pp. 89-95, Morella, Mexico.
Philip Bille, Tree Edit Distance, Alignment Distance and Inclusion, Technical Report TR-2003-23 in IT Univ. Tech.Report Series, Mar. 2003, Univ. of Copenhagen, Denmark.
Michael Strube et al., The Influence of Minimum Edit Distance on Reference Resolution, In: Empirical Methods in Natural Language Processsing, 2002, pp. 312-319.
L. Allison, Dynamic Programming Algorithm (DPA) for Edit Distance http://www.csse.monash.edu.au/˜lloyd/tildeAlgDS/Dynamic/Edit, 1999, Monash University, Australia.
Ning Xu, Global and Local Alignment via Dynamic Programming, 1999.
Andrew Tridgell et al., The Rsync Algorithm, http://samba.anu.edu.au/rsync/tech—report ACT 0200, Australian National University, Jun. 1996, Canberra, Australia.
Eugene W. Myers, An O(ND) Difference Algorithm and Its Variations. Algorithmica, 1986, pp. 1-15.
James W. Hunt et al., A Fast Algorithm for Computing Longest Subsequences. Communications of the ACM, May 1977, pp. 350-353 vol. 20, No. 5.
Michael Gilleland, Levenshtein Distance, In Three Flavors, Meriam Park Software, www.merriampark.com/id.htm, pp. 1-12, 2004-2005.
Anoop Sarkar, Multiple Sequence Alignment: A Brief Introduction. for CMPT-825: Natural Language Processing, pp. 1-3, Sep. 15, 2003.
Thomas Gagne et al., Smalltalk Pattern Matching, pp. 1-10, Nov. 11, 2004.
Anácapa North
Moll Robert
Ortiz Belix M
Rones Charles
LandOfFree
Method for computing the minimum edit distance with fine... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for computing the minimum edit distance with fine..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for computing the minimum edit distance with fine... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3895313