  In many applications, it is necessary to determine the string similarity.
Edit distance[WF74] approach is a classic method to determine Field Similarity.
A well known dynamic programming algorithm [GUS97] is used to calculate edit
distance with the time complexity O(nm). (for worst case, average case and even
best case) Instead of continuing with improving the edit distance approach,
[LL+99] adopted a brand new approach-token-based approach. Its new concept of
token-base-retain the original semantic information, good time complex-O(nm)
(for worst, average and best case) and good experimental performance make it a
milestone paper in this area. Further study indicates that there is still room
for improvement of its Field Similarity algorithm. Our paper is to introduce a
package of substring-based new algorithms to determine Field Similarity.
Combined together, our new algorithms not only achieve higher accuracy but also
gain the time complexity O(knm) (k<0.75) for worst case, O(*n) where <6 for
average case and O(1) for best case. Throughout the paper, we use the approach
of comparative examples to show higher accuracy of our algorithms compared to
the one proposed in [LL+99]. Theoretical analysis, concrete examples and
experimental result show that our algorithms can significantly improve the
accuracy and time complexity of the calculation of Field Similarity. [US97] D.
Guseld. Algorithms on Strings, Trees and Sequences, in Computer Science and
Computational Biology. [LL+99] Mong Li Lee, Cleansing data for mining and
warehousing, In Proceedings of the 10th International Conference on Database
and Expert Systems Applications (DEXA99), pages 751-760,August 1999. [WF74] R.
Wagner and M. Fisher, The String to String Correction Problem, JACM 21 pages
168-173, 1974.
