14

I have two subtitles files. I need a function that tells whether they represent the same text, or the similar text

Sometimes there are comments like "The wind is blowing... the music is playing" in one file only. But 80% percent of the contents will be the same. The function must return TRUE (files represent the same text). And sometimes there are misspellings like 1 instead of l (one - L ) as here: She 1eft the baggage. Of course, it means function must return TRUE.

My comments:
The function should return percentage of the similarity of texts - AGREE

"all the people were happy" and "all the people were not happy" - here that'd be considered as a misspelling, so that'd be considered the same text. To be exact, the percentage the function returns will be lower, but high enough to say the phrases are similar

Do consider whether you want to apply Levenshtein on a whole file or just a search string - not sure about Levenshtein, but the algorithm must be applied to the file as a whole. It'll be a very long string, though.

Improve this question
4
  • 2
    The function should return percentage of the similarity of texts and you decide the threshold for TRUE or FALSE. Commented Feb 24, 2010 at 11:37
  • You're going to need to be very thoughtful about your similarity criteria and I think this may be the toughest part of what you are trying to do. For example "all the people were happy" and "all the people were not happy" are similar textually but entirely opposite in terms of meaning. Some examples of similar and dissimilar text may be helpful. Commented Feb 24, 2010 at 11:46
  • 1
    Check out Soundex (en.wikipedia.org/wiki/Soundex) and see if that's something you're looking for. Commented Feb 24, 2010 at 11:59
  • Do consider whether you want to apply Levenshtein on a whole file or just a search string Commented Feb 24, 2010 at 12:03

6 Answers 6

Reset to default
13

Levenshtein algorithm: http://en.wikipedia.org/wiki/Levenshtein_distance

Anything other than a result of zero means the text are not "identical". "Similar" is a measure of how far/near they are. Result is an integer.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

+1: The integer result would need to be normalised to determine the similarity of the whole file. E.g. Similarity = Levenshtein Distance / Num. Characters. I would also suggest preprocessing the file to correct spelling mistakes before applying this algorithm.
There is an implementation of the Levenshtein distance in Apache Commons StringUtils: commons.apache.org/lang/api-2.4/org/apache/commons/lang/…, java.lang.String)
@Fabian: It is a builtin function in PHP: php.net/manual/en/function.levenshtein.php
Levinstain distance is not applicable for long strings. Using the StringUtils implementation, for instance, would take few minutes per file, if size of each file is ~ 300kb.
6

For the problem you've described (i.e. compering large strings), you can use Cosine Similarity, which return a number between 0 (completely different) to 1 (identical), base on the term frequency vectors.

You might want to look at several implementations that are described here: Cosine Similarity

Improve this answer

Comments

2

You're expecting too much here, it looks like you would have to write a function for your specific needs. I would recommend starting with an existing file comparison application (maybe diff already has everything you need) and improve it to provide good results for your input.

Improve this answer

3 Comments

or,render the text with a known font size (and face), and then compare pixels. that way, symbols with similar looking shape can be made to look similar, and its easier to detect that.
@Chii but on larger symbol shifting the rest of the page would throw everything of.
I don't think the question has anything to do with OCR, but just plain text
2

Have a look at approximate grep. It might give you pointers, though it's almost certain to perform abysmally on large chunks of text like you're talking about.

EDIT: The original version of agrep isn't open source, so you might get links to OSS versions from http://en.wikipedia.org/wiki/Agrep

Improve this answer

Comments

1

There are many alternatives to the Levenshtein distance. For example the Jaro-Winkler distance.

The choice for such algorithm is depending on the language, type of words, are the words entered by human and many more...

Here you find a helpful implementation of several algorithms within one library

Improve this answer

Comments

0

if you are still looking for the solution then go with S-Bert (Sentence Bert) which is light weight algorithm which internally uses cosine similarly.

Improve this answer

2 Comments

Along with this answer, adding additional supporting information will help others confirm that your answer is correct. Could you provide citations or documentation about how the similarity algorithm works? You also mentioned cosine similarity, which you may also want to site. You can find more information on how to write good answers in the help center.
Here the question which gives more details. stackoverflow.com/questions/57882417/…

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.