6

I have seen similar questions about text comparison, but none on such a large scale.

I have a client with two sets of recordings of speeches, 250 and 550 recordings each. Each of the recordings in each set are unique, but about 200 out of the 250 are duplicated in the set of 550, and they need to weed out the doubles. The recordings were recorded on separate devices, so you can't just compare the file length and content.

They are willing to pay to have the first 15 seconds of each recording transcribed, and then they want me to devise some system of using those transcripts to identify the doubles.

First of all, I'm assuming that I should first remove any punctuation and capitalization, because those are things that might arbitrarily change based on the transcriptionist who happens to do that file.

My first idea was to simply calculate the Levenshtein distance for each combination of recordings, but I can't imagine doing that on such a large scale (250 x 550) would be efficient. Then I thought that instead of doing a Levenshtein distance, but using words as the unit instead of characters. But this still would involve running an algorithm 250X550 times, albeit a much faster algorithm each time.

Then I was thinking that maybe I should go through each document, and make a alphabetically sorted dictionary with a count of how many times each word appears in each document. Then I could just go through the dictionary associated with each document and subtract the number of appearances of each word from each other, to produce a total number of mismatched words. This looses taking into account the order of the words, but it should be much faster.

Which of these methods, or perhaps an entirely different method, should I use?

Improve this question
10
  • 1
    As with many theoretical performance problems, the answer is probably going to be "build prototypes and benchmark them." Have you actually tried doing any of these methods to see if they really are too slow?
    – Ixrec
    Jun 3, 2015 at 20:35
  • @Ixrec I haven't received any transcripts to experiment with yet, but I figured I would prepare in advance.
    – clum
    Jun 3, 2015 at 20:37
  • If you want data to prepare in advance just go to wikiquote.com and get all the quotes by, say, Albert Einstein, along with all their variations. If you can detect which ones are variations of others, you are set.
    – Mike Nakis
    Jun 3, 2015 at 20:39
  • @Ixrec Actually, though perhaps I gave that impression in the question, I'm not really asking in terms of performance. I am also concerned about accuracy and difficulty of implementation, which are both very important. Obviously Levenshtein will be the most accurate, but my question is whether there are alternate implementations that would be accurate enough.
    – clum
    Jun 3, 2015 at 20:41
  • Keep in mind that the first 15 seconds will only contain a handful of words or sentences.
    – rwong
    Jun 3, 2015 at 20:41

2 Answers 2

Reset to default
10

For one-shot reports like this, accuracy of results and ease of verifying your algorithm are way, way more important than efficiency. Your brute force algorithm is only 137,500 combinations, comparing maybe a couple dozen words each. That's a runtime on the order of a few seconds, assuming you read all the transcripts into memory first. That's nothing compared to the hours spent doing the transcription and your own time. Even if it took an hour to run, that would be better than a fast algorithm that you weren't sure would work. Don't make this harder on yourself.

Improve this answer
2
  • +1 In this case why would a day, (or week or a month) to get a reliable result be a problem? In the 1960's computers were billed based on CPU time used and a day of CPU time might have been more expensive than doing it by hand, we have moved on from that era, CPU time is cheaper, developer time not.....
    – mattnz
    Jun 4, 2015 at 4:51
  • Makes sense. I'll let you know how it goes (and, presumably, accept this answer) when I try it out in practice.
    – clum
    Jun 4, 2015 at 11:07
1

The run time for the edit distance calculations is trivial, but I'd be concerned that the results will be poor. Character-by-character will be noisy; I'd be amazed if you got any exact matches. Word-by-word will be subject to the vagaries of erroneously hearing a plural, homophones, etc, etc.

That said, nothing wrong with trying the simplest possible thing first. If the results aren't good enough, though next I'd try:

  1. Splitting the string up, run a simple stemming algorithm on the words, and then do the edit distance calculations. https://pypi.python.org/pypi/stemming/1.0 for example.
  2. If that doesn't produce clean enough results, I'd fall back to the vector space document model which you could easily implement for your purposes, in 20-30 lines of most high level languages. (Or pull out the heavy guns and shove it into Lucene.)
Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.