A two-step string-matching procedure

摘要

String-matching algorithms which will be used as part of a knowledge-based retrieval system for multimedia documents, consisting of the graphical images of corporate trademarks, trademark words or phrases, and representations of companies and products, are discussed. Let LLCS(A, B) denote the length of the longest common subsequence of two strings A and B. We describe an improvement to the Wagner-Fischer Algorithm called WF+ for finding the LLCS which runs in linear space and quadratic time. An approximate algorithm for finding the LLCS, called the sorted string approximate algorithm (SSAA), is then presented, which runs in linear time but works on strings in sorted order only. The SSAA and WF+ are then combined into a two-step process which retrieves strings similar to a given string in near-linear time. Empirical data are presented in support of the estimates of average running time for the algorithms.