一道算法题

Question

我现在做字幕对齐的工作，现在有两个list的字符串，比如说listA，和listB。 listA是人工打出来的字幕，listB，是把语音切分成片，识别出来文字，准确率不是很高，listB中包含语音的时间戳信息。我要做事情就是给listA打上时间戳。 我现在有个基本的想法，不知道大家能不能提出更好的思路，希望集思广益一下。

这个是实验室帮助聋人看电视节目做的项目。

对于felix021的回答，提到的compare的实现，这个是最基本的工作，相似度 度量不行，后面的工作无法开展。我最开始的想法是用jaccard，或者编辑距离的倒数。编辑距离是不行的，比对后结果多为两个字符串的长度。jaccard距离，是用两个字符串的交除以两个字符串的并，这种度量方式稍微靠谱点，大概0.2以上的准确率还行。
用最简单的找最大相似度的方法，效果不是特别好。我想可以从两个方面来提高，

• 提高相似度算法，更好的度量两个字符串的相似度。jaccard只是取了两个字符串中字符的交集，显然这里面还有更多的信息没有被挖掘，如连续字符串，词频（的，乒），拼音，句子的长度（句子很长，但已经有6个词相同了，其实他们相似的概率已经很高了，但是因为句子长，又被降低了)... 希望大家可以想一想还有什么方法可以提高相似度算法
• listA 和 listB是按照时间排列的，如果listA[i] he listB[j]的相似度非常高，则listA[i+1]和listB[j+1]匹配的可能性也会变高。所以遇到这种情况，我们可以通过（i,j）传递一点能量给(i+1,j+1). 这里需要设计一个传递函数。

另外一个问题，我们会遇到有些句子在listA和listB中得不到匹配情况，这种情况就需要平滑处理。不知道这种两个流动的字符串匹配，有没有些成熟的算法。 我现在的想法是把两个list看成，编辑距离中两个个字符串，这样编辑距离中的字符变成了list里的字符串。 也同样有delete，insert，match三种操作，三种操作的代价是他们的相似度，而不是一个固定值1。
这是我目前的想法，但感觉这个问题，前人应当遇到过，想借鉴一下。 因为人工打出来的文本有很多错误，识别的结果错误更多，希望可以设计一个比较健壮的算法，把准确率提升上去。

Answer 1

基本思路应该是这样吧：

def find_n_most_likely(textB, listA, n):
    Similarity = [compare(textA, textB) for textA in listA]
    Similarity.sort()
    return Similarity[0:n]

for timestamp, text in listB:
    print find_n_most_likely(text, listA, 3) #for later revise

关键就在于这个compare怎么实现。最简单的方法就是逐字（如中文）、逐词（如英文）比较，具体比较算法可以用lcs或者编辑距离这种。鉴于listB中的text是语音识别出来的，所以还是有很多提升空间的，比如对于中文，可以考虑每个字的拼音，把拼音的相似度作为参考依据等等。