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.

Yonatan
  • 2,543
  • 2
  • 19
  • 20
EugeneP
  • 11,783
  • 32
  • 96
  • 142
  • 2
    The function should return percentage of the similarity of texts and you decide the threshold for TRUE or FALSE. – YOU Feb 24 '10 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. – glenatron Feb 24 '10 at 11:46
  • 1
    Check out Soundex (http://en.wikipedia.org/wiki/Soundex) and see if that's something you're looking for. – Buhake Sindi Feb 24 '10 at 11:59
  • Do consider whether you want to apply Levenshtein on a whole file or just a search string – bcosca Feb 24 '10 at 12:03

6 Answers6

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.

bcosca
  • 17,371
  • 5
  • 40
  • 51
  • 2
    +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. – Adamski Feb 24 '10 at 11:48
  • There is an implementation of the Levenshtein distance in Apache Commons `StringUtils`: http://commons.apache.org/lang/api-2.4/org/apache/commons/lang/StringUtils.html#getLevenshteinDistance(java.lang.String, java.lang.String) – Fabian Steeg Feb 24 '10 at 11:56
  • 2
    @Fabian: It is a builtin function in PHP: http://php.net/manual/en/function.levenshtein.php – soulmerge Feb 24 '10 at 13:16
  • 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. – Yonatan Nov 06 '11 at 13:54
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

Community
  • 1
  • 1
Yonatan
  • 2,543
  • 2
  • 19
  • 20
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

Chinmay Kanchi
  • 62,729
  • 22
  • 87
  • 114
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.

Dominic Rodger
  • 97,747
  • 36
  • 197
  • 212
soulmerge
  • 73,842
  • 19
  • 118
  • 155
  • 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 Feb 24 '10 at 11:42
  • @Chii but on larger symbol shifting the rest of the page would throw everything of. – Jens Schauder Feb 24 '10 at 11:45
  • I don't think the question has anything to do with OCR, but just plain text – bcosca Feb 24 '10 at 12:16
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

Community
  • 1
  • 1
Philipp
  • 4,645
  • 3
  • 47
  • 80
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.

balu datascience
  • 71
  • 1
  • 4
  • 1
    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](https://stackoverflow.com/help/how-to-answer). – charlie-map Mar 23 '22 at 03:03
  • Here the question which gives more details. https://stackoverflow.com/questions/57882417/is-it-possible-to-use-google-bert-to-calculate-similarity-between-two-textual-do – balu datascience Mar 28 '22 at 14:25