hansjorn

轉(zhuǎn)載：https://blog.csdn.net/qq_45066628/article/details/123170726，這里僅當學(xué)習(xí)，建議去原文查看學(xué)習(xí)。

前言
最近由于要對OCR文字識別系統(tǒng)的表格識別部分做指標評測分析。評測方法之前是將ground truth 和recognition result 展平后統(tǒng)計非空單元格之間的兩兩關(guān)系，得到非空單元格的關(guān)系矩陣。然后基于這個矩陣去統(tǒng)計Recall，Precision和 F1 score。但是這樣的評測方式是有問題的：

只檢查非空單元格之間的直接關(guān)系，而對于由空單元格和非直接關(guān)系單元格之間未對齊引起的錯誤無法檢測。

另一個問題是無法同時對單元格的內(nèi)容進行評測

經(jīng)過一番搜索發(fā)現(xiàn)了TEDS評價方法

TEDS介紹
TEDS評價是將表格結(jié)構(gòu)用樹狀結(jié)構(gòu)表示，樹的root節(jié)點下有兩個children節(jié)點thead(表格頭)和tbody(表格體)，thead和tbody的children節(jié)點是tr（表格行），樹的葉子節(jié)點是td(單元格)，每個葉子節(jié)點包含三種屬性rowspan（行跨度），colspan（列跨度），content（單元格內(nèi)容）。采用樹的距離來進行兩顆樹之間相似度的度量的一種方法。

公式如下：

編輯距離相似度(teds)=1-編輯距離(editdist)/max(字符串1長度，字符串2的長度)

編輯距離
編輯距離（Edit Distance），又稱Levenshtein距離，俄羅斯科學(xué)家Vladimir Levenshtein在1965年提出這個概念，又叫 Levenshtein 距離。是指兩個字串之間，由一個轉(zhuǎn)成另一個所需的最少編輯操作次數(shù)。許可的編輯操作包括將一個字符替換成另一個字符，插入一個字符，刪除一個字符。如比較S1=“內(nèi)審協(xié)會”和s2=“中國內(nèi)審協(xié)會”，就可以通過在S1中插入“中”、“國”兩個漢字實現(xiàn)與S2一直，故S1和S2編輯距離為2。

其核心算法：

設(shè)計一個二維表格，表格列數(shù)為字符串1的長度加1，行數(shù)為字符串2的長度加1。
表格的第1行按照列，自左往右，依序填列0,1,2，…字符串1的長度n;
表格的1列按照行，自上往下，依序填列0,1,2，…字符串2的長度m;
然后自第2行，第2列開始，自左往右，填充數(shù)據(jù)，
該數(shù)據(jù)的規(guī)則是：如果兩個字符串對應(yīng)位置的字符相同，則取左上角單元格的值；如果不同，則取該單元格左方、左上方、上方的三個但單元格的值的最小值+1。重復(fù)上述操作，直到填滿最后一個單元格，其數(shù)字就是編輯距離。

https://i-blog.csdnimg.cn/blog_migrate/514b365f05b5be1252f64a55fc6f0548.gif#pic_center

python實現(xiàn)方式

第一種

def minDistance(word1, word2):
    if not word1:
        return len(word2 or '') or 0

    if not word2:
        return len(word1 or '') or 0

    size1 = len(word1)
    size2 = len(word2)

    last = 0
    tmp = range(size2 + 1)
    value = None

    for i in range(size1):
        tmp[0] = i + 1
        last = i
        # print word1[i], last, tmp
        for j in range(size2):
            if word1[i] == word2[j]:
                value = last
            else:
                value = 1 + min(last, tmp[j], tmp[j + 1])
                # print(last, tmp[j], tmp[j + 1], value)
            last = tmp[j+1]
            tmp[j+1] = value
        # print tmp
    return value

測試

assert minDistance('horse', '') == 5
assert minDistance('', 'ros') == 3

assert minDistance('h', 'r') == 1
assert minDistance('horse', 'ros') == 3

第二種,基于Python-Levenshtein

pip install python-Levenshtein
所有用法：

#關(guān)于 Levenshtein 所有函數(shù)的用法和注釋
apply_edit() #根據(jù)第一個參數(shù)editops（）給出的操作權(quán)重，對第一個字符串基于第二個字符串進行相對于權(quán)重的操作
distance() #計算2個字符串之間需要操作的絕對距離
editops() #找到將一個字符串轉(zhuǎn)換成另外一個字符串的所有編輯操作序列
hamming() #計算2個字符串不同字符的個數(shù)，這2個字符串長度必須相同
inverse() #用于反轉(zhuǎn)所有的編輯操作序列
jaro() #計算2個字符串的相識度，這個給與相同的字符更高的權(quán)重指數(shù)

jaro_winkler() #計算2個字符串的相識度，相對于jaro 他給相識的字符串添加了更高的權(quán)重指數(shù)，所以得出的結(jié)果會相對jaro更大（%百分比比更大）
matching_blocks() #找到他們不同的塊和相同的塊，從第六個開始相同，那么返回截止5-5不相同的1，第8個后面也開始相同所以返回8-8-1，相同后面進行對比不同，最后2個對比相同返回0
median() #找到一個列表中所有字符串中相同的元素，并且將這些元素整合，找到最接近這些元素的值，可以不是字符串中的值。
median_improve() #通過擾動來改進近似的廣義中值字符串。

opcodes() #給出所有第一個字符串轉(zhuǎn)換成第二個字符串需要權(quán)重的操作和操作詳情會給出一個列表，列表的值為元祖，每個元祖中有5個值
#[('delete', 0, 1, 0, 0), ('equal', 1, 3, 0, 2), ('insert', 3, 3, 2, 3), ('replace', 3, 4, 3, 4)]
#第一個值是需要修改的權(quán)重，例如第一個元祖是要刪除的操作,2和3是第一個字符串需要改變的切片起始位和結(jié)束位，例如第一個元祖是刪除第一字符串的0-1這個下標的元素
#4和5是第二個字符串需要改變的切片起始位和結(jié)束位，例如第一個元祖是刪除第一字符串的0-0這個下標的元素，所以第二個不需要刪除

quickmedian() #最快的速度找到最相近元素出現(xiàn)最多從新匹配出的一個新的字符串
ratio() #計算2個字符串的相似度，它是基于最小編輯距離
seqratio() #計算兩個字符串序列的相似率。
setmedian() #找到一個字符串集的中位數(shù)(作為序列傳遞)。 取最接近的一個字符串進行傳遞，這個字符串必須是最接近所有字符串，并且返回的字符串始終是序列中的字符串之一。
setratio() #計算兩個字符串集的相似率(作為序列傳遞)。
subtract_edit() #從序列中減去一個編輯子序列。看例子這個比較主要的還是可以將第一個源字符串進行改變，并且是基于第二個字符串的改變，最終目的是改變成和第二個字符串更相似甚至一樣

def TEDS(str1,str2):
    maxL=len(str1)
    if len(str2)>maxL:
        maxL=len(str2)
    distan=ls.distance(str1,str2)
    teds_result=100-distan/maxL*100
    return teds_result

原文鏈接：https://blog.csdn.net/qq_45066628/article/details/123170726