Similarity of two texts (adaptive local alignment of keywords?)

Question

Hi!

I have 2 texts (max 4000 characters) of different length. And I need to get a similarity rate based on (partial-)paraphrasing. Please note that same portion of texts can be in different position in each text (So Levenshtein is not the solution).

The comparison process should also:

• not increase expo. with text size
• be performance friendly. :)

It seems that the "adaptive local alignment of keywords" is a possible solution.

Do you have any implementation example? Preferred language is PHP but I can translate. :)

Do you have any other solution/idea/experience on that topic?

Thanks for your great help.

Answer 1

Take a look at the levenshtein and similar_text functions which should make your life easier:

• http://us2.php.net/manual/en/function.levenshtein.php
• http://us2.php.net/manual/en/function.similar-text.php

EDIT: @Toto has pointed out that those may not be suitable for this application, see his comments below.

Answer 2

Needleman-Wunsch worked quite well for an application where I had to match names given to the same thing by different people.