成福春,張平,劉華,房敏
1.上海中醫(yī)藥大學(xué)附屬岳陽(yáng)中西醫(yī)結(jié)合醫(yī)院,上海 200437;2.上海中醫(yī)藥大學(xué)附屬曙光醫(yī)院,上海 201203
SNOMED編碼校驗(yàn)位算法解析及其對(duì)中醫(yī)術(shù)語(yǔ)編碼的意義
成福春1,張平2*,劉華1,房敏1
1.上海中醫(yī)藥大學(xué)附屬岳陽(yáng)中西醫(yī)結(jié)合醫(yī)院,上海 200437;2.上海中醫(yī)藥大學(xué)附屬曙光醫(yī)院,上海 201203
本文討論了編碼之中常用到的按位累加取模、多項(xiàng)式乘法累加取模等校驗(yàn)位算法的優(yōu)缺點(diǎn),尤其是對(duì)系統(tǒng)化醫(yī)學(xué)術(shù)語(yǔ)集(SNOMED)編碼采用二面體群D5校驗(yàn)位算法作了較深入的討論。二面體群D5算法不僅可以校驗(yàn)出所有一位錯(cuò)誤及相鄰位置換位錯(cuò)誤,而且不需要增加字母 X,是一種非常理想的校驗(yàn)位算法。國(guó)內(nèi)目前尚無(wú)一套既具有信息技術(shù)特征,又具有中醫(yī)學(xué)科本身特征的編碼化的術(shù)語(yǔ)集,SNOMED編碼采用二面體群D5校驗(yàn)位算法,對(duì)于中醫(yī)術(shù)語(yǔ)編碼具有重要的借鑒意義。
中醫(yī)術(shù)語(yǔ);術(shù)語(yǔ)編碼;系統(tǒng)化醫(yī)學(xué)術(shù)語(yǔ)集;校驗(yàn)位算法;二面體群D5
醫(yī)學(xué)術(shù)語(yǔ)及其編碼化,對(duì)于規(guī)范臨床數(shù)據(jù)采集,數(shù)據(jù)檢索分析利用、提升醫(yī)療質(zhì)量以及研究的深度,具有重要意義[1]。系統(tǒng)化醫(yī)學(xué)術(shù)語(yǔ)集-臨床術(shù)語(yǔ)( systematized nomenclature of medicineclinical terms, SNOMED CT)通過(guò)編碼進(jìn)行世界范圍內(nèi)的統(tǒng)一術(shù)語(yǔ)交流,即代碼唯一,或稱概念唯一。但是代碼所代表的內(nèi)容其形式可以多樣,如英文形式、中文形式或者各國(guó)語(yǔ)言形式。通過(guò)定義代碼與代碼之間的關(guān)系,來(lái)體現(xiàn)學(xué)科本身的邏輯與語(yǔ)義。
在SNOMED CT術(shù)語(yǔ)體系中,賦予每一個(gè)特定術(shù)語(yǔ)一個(gè)代碼,即擴(kuò)展版的SNOMED CT概念標(biāo)識(shí)符(SCTID字段)。代碼本身不要求有特別的含義,只是代表這個(gè)術(shù)語(yǔ)本身,利于計(jì)算機(jī)處理。
在代碼結(jié)構(gòu)中,具有相關(guān)的屬性信息,如extension item identifier(擴(kuò)展項(xiàng)目標(biāo)識(shí)符),共8位,代表具體的項(xiàng)目編碼;namespace identifier(名稱空間標(biāo)識(shí)符),共7位,代表維護(hù)代碼的機(jī)構(gòu);partition identifier(部分標(biāo)識(shí)符),2位,10代替概念,20代表描述,30代表關(guān)系;最后一位是check-digit(校驗(yàn)位),便于計(jì)算機(jī)自動(dòng)糾錯(cuò)。SNOMED通過(guò)3張表來(lái)體現(xiàn),即概念表、定義表、關(guān)系表。SCTID是概念表中的最重要的字段。目前擴(kuò)展版的SCTID字段結(jié)構(gòu)如圖1。

圖1 擴(kuò)展版的SCTlD數(shù)字編碼結(jié)構(gòu)
雖然用戶可能很少手工錄入SCTID,但是還是有可能會(huì)發(fā)生這種情況。在手工錄入過(guò)程中,由于數(shù)字串太長(zhǎng),不可避免地會(huì)發(fā)生數(shù)據(jù)錄入錯(cuò)誤。而通過(guò)校驗(yàn)位,能夠大大減少數(shù)據(jù)錄入錯(cuò)誤。
J Verhoeff[2]基于對(duì)手工錄入時(shí)發(fā)生的 12 000個(gè)錯(cuò)誤的研究,將人們常犯的錯(cuò)誤進(jìn)行總結(jié),共分為7類。⑴單個(gè)錯(cuò)誤,a變成b,在所有錯(cuò)誤中約占60%~95%。⑵遺漏或增加 1個(gè)數(shù)字,占所有錯(cuò)誤的 10%~20%。⑶換位錯(cuò)誤,ab變成ba,占所有錯(cuò)誤的10%~20%。⑷雙子錯(cuò)誤,如aa變成bb,占所有錯(cuò)誤的0.5%~1.5%。⑸跳躍轉(zhuǎn)換,如acb變成bca,占所有錯(cuò)誤的0.5%~1.5%。⑹跳躍雙子錯(cuò)誤,如aca變成bcb,發(fā)生率<1%。⑺發(fā)音錯(cuò)誤,如1a與a0,英文的13與30、14與40、15與50等,發(fā)生率約0.5%。
可以看出,人們?cè)谔幚頂?shù)字錯(cuò)誤時(shí),常犯的錯(cuò)誤以一位為主。因此,考慮增加校驗(yàn)位,針對(duì)一位錯(cuò)誤,設(shè)計(jì)相應(yīng)的算法,成為校驗(yàn)位研究的主要內(nèi)容。
2.1 按位累加取模
常見(jiàn)的模(除數(shù))為7、9、11、13等質(zhì)數(shù),因其每一位余數(shù)均與該模互質(zhì)。按位累加取模,賦予校驗(yàn)位。在驗(yàn)證時(shí),按同樣算法進(jìn)行比較,相等說(shuō)明編碼正確,不等則編碼有誤。
優(yōu)點(diǎn)是算法簡(jiǎn)單,可以校驗(yàn)出大部分一位錯(cuò)誤。缺點(diǎn)是累加取模,無(wú)位置信息,不能判斷出相鄰轉(zhuǎn)換錯(cuò)誤,如ab變成ba。當(dāng)模的數(shù)字<10時(shí),會(huì)出現(xiàn)相關(guān)重復(fù)錯(cuò)誤情況,導(dǎo)致不能檢測(cè)出所有單個(gè)錯(cuò)誤,如取模為 7 的7與0、8與1、9與2,取模為9的9與0等。
2.2 多項(xiàng)式乘法校驗(yàn)位算法
原理為 K元組的點(diǎn)乘和取余,即(a1,a2……ak)·(w1,w2……wk) mod m=(a1w1+a2w2+……akwk) mod m=0。常見(jiàn)的模m為10或11。
2.2.1 取模m為10 UPC編碼(universal product code)是最早大規(guī)模應(yīng)用的條碼,為長(zhǎng)度固定、連續(xù)性的條碼,主要在美國(guó)和加拿大使用,由于其應(yīng)用范圍廣泛,故又被稱為萬(wàn)用條碼。UPC編碼僅可用來(lái)表示數(shù)字,故其字碼集為數(shù)字0~9。在UPC編碼中,a1、a2……a12滿足以下等式:(a1,a2,……,a12)·(3,1,3,1……3,1) mod 10=0,a12為校驗(yàn)位值。
優(yōu)點(diǎn)是可以檢測(cè)出所有的單個(gè)錯(cuò)誤,也可以檢測(cè)出ab變成ba這種相鄰位置換位錯(cuò)誤。缺點(diǎn)是不能檢測(cè)出abc變成cba這種錯(cuò)誤,也不能檢測(cè)出|a-b|=5的交換錯(cuò)誤[3]。
2.2.2 取模m為11 模為11時(shí),余數(shù)為0,1,2,3,4,5,6,7,8,9,10。當(dāng)余數(shù)為10時(shí),為了不增加位數(shù),往往用X來(lái)代替。如國(guó)際圖書(shū)編碼ISBN 號(hào)0-669-19493,校驗(yàn)位X,代表10,校驗(yàn)位a10滿足(a1,a2,……,a9,a10)·(10,9,8,7,6,5,4,3,2,1)mod 11=0。
優(yōu)點(diǎn)是可以檢測(cè)出所有一位錯(cuò)誤及相鄰位置換位錯(cuò)誤。缺點(diǎn)是增加了字母X,使編碼不再是純數(shù)字,在信息系統(tǒng)定義數(shù)據(jù)類型方面存在不便。由于在計(jì)算機(jī)表示中,數(shù)字的表示與字母的表示存在著差別,將兩者合在一起來(lái)表示某一特定的編碼,無(wú)疑增加了算法處理的復(fù)雜性,增加了系統(tǒng)設(shè)計(jì)及改造的成本,增加了系統(tǒng)處理的難度以及社會(huì)使用成本。
我國(guó)的身份證校驗(yàn)位算法即使用上述算法。根據(jù)中華人民共和國(guó)國(guó)家標(biāo)準(zhǔn)GB 11643-1999中有關(guān)公民身份號(hào)碼的規(guī)定,公民身份號(hào)碼是特征組合碼,由17位數(shù)字本體碼和1位數(shù)字校驗(yàn)碼組成。排列順序從左至右依次為6位數(shù)字地址碼、8位數(shù)字出生日期碼、3位數(shù)字順序碼和1位數(shù)字校驗(yàn)碼。校驗(yàn)位根據(jù)前面17位數(shù)字碼,按照ISO 7064:1983.MOD 11-2編碼規(guī)則∑(ai×wi)mod 11計(jì)算。其中,i表示號(hào)碼字符從右至左包括校驗(yàn)碼在內(nèi)的位置序號(hào);ai表示第i位置上的號(hào)碼字符值;wi表示第i位置上的加權(quán)因子,其數(shù)值依據(jù)公式是wi=2(i-1)mod 11。
以某男性公民身份證號(hào)碼為例,其本體碼為34052419800101001,按照上述公式計(jì)算,見(jiàn)表1。

根據(jù)計(jì)算結(jié)果,從表2中查出,計(jì)算結(jié)果為2的校驗(yàn)碼為 X,所以該男性公民身份證號(hào)碼應(yīng)該為34052419800101001X。

表1 某男性公民身份證校驗(yàn)位算法表

表2 身份證取模m為11的余數(shù)與校驗(yàn)碼對(duì)照表
法國(guó)天才數(shù)學(xué)家伽羅瓦于1822年首次提出“群”的概念,目的是解決高次方程有無(wú)定解以及解的表示問(wèn)題。如一個(gè)正四邊形,其旋轉(zhuǎn)90°、180°、270°、360°,形狀仍與原來(lái)的形狀重合;而其左右對(duì)角線、水平及垂直平分線均反射對(duì)稱。抽象出來(lái),具有旋轉(zhuǎn)對(duì)稱與反射對(duì)稱的正n邊形,稱為二面體。旋轉(zhuǎn)與對(duì)稱被稱為二元運(yùn)算中的元素。它的各種變換可以由置換群來(lái)表示,其相應(yīng)的變換迭加后得到的元素仍在群中。群是抽象代數(shù)研究的最主要內(nèi)容。這種不再以單純的數(shù)字的加減,而以數(shù)據(jù)的結(jié)構(gòu)為主要的研究?jī)?nèi)容,是抽象代數(shù)的一個(gè)本質(zhì)特征。
二面體群 D5,以正五邊形為例,考慮其旋轉(zhuǎn)對(duì)稱,將360°分為5份,則分別是72°、144°、216°、288°、360°(或 0°)。而對(duì)稱變換,則以某一個(gè)頂點(diǎn)作垂直于頂點(diǎn)所對(duì)的邊的垂直平分線。這時(shí),會(huì)發(fā)生頂點(diǎn)相關(guān)位置的交換。
對(duì)此作Calay(凱萊)乘法表,0代表旋轉(zhuǎn)0° 或360°,1代表旋轉(zhuǎn)72°,2代表旋轉(zhuǎn)144°,3代表旋轉(zhuǎn)216°,4代表旋轉(zhuǎn)288°,5代表以正五邊形的頂點(diǎn)A作反射對(duì)稱變換,6代表以正五邊形的頂點(diǎn)B作反射對(duì)稱變換,以此類推。表中的具體數(shù)值是某兩個(gè)變換疊加的結(jié)果(兩個(gè)元素相乘),在二面體群D5乘法表中(見(jiàn)表3),3與6的相乘,結(jié)果為9,表示正五邊形的起始狀態(tài),經(jīng)過(guò)旋轉(zhuǎn)216°,再以A點(diǎn)作對(duì)稱變換,其結(jié)果與起始位置直接作 E點(diǎn)對(duì)稱變換,結(jié)果是一樣的。如此則可以完全表示出二面體群D5的變化規(guī)律。其各種復(fù)雜的變化規(guī)律都是以上基礎(chǔ)規(guī)律的迭加。因此,可以利用連續(xù)變換的方法,得出最終的一個(gè)狀態(tài)。
J Verhoeff于1969年開(kāi)發(fā)出了基于二面體群D5的校驗(yàn)位算法。考慮數(shù)字串a(chǎn)1a2……an-1,增加1位校驗(yàn)位an,滿足an*σ(a1)*σ2(a2)*σ3(a3)*……σ(n-1)(an-1)=0。這里σ2(x)=σ(σ(x)),σ3(x)=σ(σ2(x))。以此類推。由于如果 a≠b,σ有著σi(a)≠σi(b)。所有的單個(gè)數(shù)字錯(cuò)誤均被檢出。這里,σ代表某種置換,*代表二面體群D5乘法運(yùn)算。二面體群D5乘法表見(jiàn)表3。

表3 二面體群D5乘法表
又由于,如果a≠b,a*σ(b)≠b*σ(a),可以推出σi(a)*σ(i+1)(b)≠σi(b)*σ(i+1)(a),因此,所有的包括相鄰位置的交換錯(cuò)誤均被檢出。
表4為變換如σ=(01589427)(36)形成的置換表。
SNOMED CT中的SCTID,即采用了二面體群D5算法進(jìn)行校驗(yàn)[4]。如 SNOMED CT(RF1)中的代碼138875005,代表SNOMED CT Concept,其最后的“5”是校驗(yàn)位,是根據(jù)前面8個(gè)數(shù)字,通過(guò)二面體D5校驗(yàn)位算法得出的數(shù)值。
首先,設(shè) a0為校驗(yàn)位,將數(shù)字串倒序排列為a000578831,依據(jù)等式:a0*σ1(0)*σ2(0)*σ3(5)*σ4(7)*σ5(8)*σ6(8)*σ7(3)*σ8(1)=0
按照表4,得出a0*1*5*4*8*0*1*6*1=0
從右邊開(kāi)始計(jì)算,


最后,產(chǎn)生完整的編碼:138875005。

表4 置換表σ=(01589427)(36)
J Verhoeff的校驗(yàn)捕獲了所有的單個(gè)錯(cuò)誤、所有的相鄰交換錯(cuò)誤、>95%的雙子錯(cuò)誤、>94%的跳躍轉(zhuǎn)換與跳躍雙子錯(cuò)誤,及大多數(shù)的元音錯(cuò)誤。因此,與mod 11一樣,減少校驗(yàn)錯(cuò)誤至2%~3%,但是不需要增加X(jué)[5-6]。
編碼的目的在于應(yīng)用,在于方便地被計(jì)算機(jī)處理。通過(guò)校驗(yàn)位算法,不僅可以判斷是否存在輸入錯(cuò)誤,也可以判斷是否是有效的編碼,從而提高實(shí)際應(yīng)用的準(zhǔn)確性。代碼的準(zhǔn)確性是代碼應(yīng)用的基礎(chǔ),而校驗(yàn)位對(duì)于代碼錄入準(zhǔn)確性的提高,起到了重要的作用。從而使后續(xù)基于代碼的若干應(yīng)用成為可能。與條形碼、二維碼等結(jié)合起來(lái),便捷地進(jìn)行數(shù)據(jù)錄入,可順暢地實(shí)現(xiàn)信息化的各種流程。
在實(shí)際進(jìn)行中醫(yī)術(shù)語(yǔ)編碼過(guò)程中,可以考慮按機(jī)構(gòu)、分類、序號(hào)進(jìn)行編碼,通過(guò)算法產(chǎn)生完整編碼并發(fā)布。而對(duì)于中醫(yī)術(shù)語(yǔ)服務(wù)平臺(tái)而言,可以提供編碼服務(wù)、編碼校驗(yàn)服務(wù)等相關(guān)功能[7]。
準(zhǔn)確而統(tǒng)一的編碼也是知識(shí)庫(kù)構(gòu)建的基礎(chǔ),知識(shí)庫(kù)的構(gòu)建依賴于無(wú)歧義的編碼。如某一個(gè)診斷,可能是某幾個(gè)癥狀的集合,體現(xiàn)為某一個(gè)編碼可以分解為另外幾個(gè)編碼的集合。
曾有觀點(diǎn)認(rèn)為,中醫(yī)本質(zhì)上是術(shù)語(yǔ),術(shù)語(yǔ)規(guī)范了,中醫(yī)也就規(guī)范了。這句話可能不夠全面,但是有著很深的道理。對(duì)于任何一門(mén)學(xué)科而言,都可以理解為本質(zhì)上是數(shù)據(jù),數(shù)據(jù)規(guī)范了,學(xué)科本身也就規(guī)范了。而對(duì)于計(jì)算機(jī)而言,更有意義的是基于術(shù)語(yǔ)的編碼,以及編碼與編碼之間的關(guān)系。
縱觀中醫(yī)發(fā)展史,數(shù)學(xué)內(nèi)容較少,這也是中醫(yī)發(fā)展步伐較慢的根本原因。不能從相關(guān)數(shù)據(jù)中獲取得到模型,不能進(jìn)行有效的驗(yàn)證,不能摒棄錯(cuò)誤或不正確的理論,發(fā)展就會(huì)緩慢,這主要是受當(dāng)時(shí)的環(huán)境條件所限。但是,如今到了信息社會(huì),網(wǎng)絡(luò)高度發(fā)達(dá),可以進(jìn)行大規(guī)模的數(shù)據(jù)采集與分析,進(jìn)行群體研究,從宏觀療效到微觀機(jī)制更加深入地研究,這些為中醫(yī)的現(xiàn)代化以及中醫(yī)自身的進(jìn)步與突破提供了可能。對(duì)于計(jì)算機(jī)而言,體現(xiàn)數(shù)據(jù)質(zhì)量與效率之處,莫過(guò)于中醫(yī)自身規(guī)范而統(tǒng)一的術(shù)語(yǔ)編碼體系。
二面體群D5以其具有全反對(duì)稱映射的10個(gè)數(shù)字最小組合,在數(shù)字編碼中具有重要意義。而校驗(yàn)位的另一個(gè)重要作用是具有防偽功能,如信用卡號(hào)的3個(gè)校驗(yàn)位,以及部分國(guó)家的紙幣編碼。
目前,國(guó)內(nèi)尚無(wú)一套既具有信息技術(shù)特征,又具有中醫(yī)學(xué)科本身特征的醫(yī)學(xué)術(shù)語(yǔ)集。而其中的編碼,是中醫(yī)術(shù)語(yǔ)集制定過(guò)程中的重要內(nèi)容。二面體群 D5校驗(yàn)位算法,是SNOMED編碼所采用的算法,對(duì)中醫(yī)術(shù)語(yǔ)集體系結(jié)構(gòu)的制定具有非常重要的借鑒意義。
但是,要對(duì)其進(jìn)行深入研究,需要解決以下3個(gè)問(wèn)題。
第一,σ=(01589427)(36)如何產(chǎn)生,有無(wú)其他的置換序列。回答這個(gè)問(wèn)題,需要理解全反對(duì)稱映射這個(gè)概念,即如果a≠b,a*σ(b)≠b*σ(a)。筆者通過(guò)設(shè)計(jì)相應(yīng)算法,找到了34 040個(gè)全反對(duì)稱映射,0~9這10個(gè)數(shù)字的全排列10!為3 628 800,34 040個(gè)全反對(duì)稱映射占其 0.938%。如(01572)(496),(0284316),(0519324678),(1932758)(46)等。這使得中醫(yī)術(shù)語(yǔ)的編碼可以不再局限于已有的SNOMED編碼置換序列。
第二,如何產(chǎn)生出字母與數(shù)字組合的校驗(yàn)位算法。二面體群 D18可以解決英文字符與數(shù)字混合的校驗(yàn)位編碼問(wèn)題,但需要對(duì)其全反對(duì)稱序列查找設(shè)計(jì)相應(yīng)的算法。
第三,變換序列的分類以及校驗(yàn)準(zhǔn)確度的評(píng)估問(wèn)題。針對(duì)前文中提到的常犯的7類錯(cuò)誤,需要對(duì)每一類變換能夠解決各種錯(cuò)誤的錯(cuò)誤率進(jìn)行分析。
而對(duì)于一位數(shù)字的糾錯(cuò),可以采用兩位校驗(yàn)位算法,不僅可以確定一位數(shù)字的錄入錯(cuò)誤,而且可以確定是哪一個(gè)位置發(fā)生錯(cuò)誤,從而可自動(dòng)糾正一位數(shù)字錯(cuò)誤。這些問(wèn)題,都是后續(xù)研究的重要內(nèi)容。
[1] 成福春,劉華,房敏.基于 SNOMED術(shù)語(yǔ)編碼兩節(jié)點(diǎn)之間多路徑算法的實(shí)現(xiàn)及其對(duì)中醫(yī)術(shù)語(yǔ)編碼的意義[J].中國(guó)中醫(yī)藥圖書(shū)情報(bào)雜志,2014, 38(1):9-12.
[2] J Verhoeff. Error Detecting Decimal Codes[M]. Amsterdam: The Mathematical Center,1969.
[3] J A Gallian. The Mathematics of Identification Numbers[J]. The College Mathematics Journal,1991,22(3):194-202.
[4] International Health Terminology Standards Development Organization. SNOMED CT Technical Implementation Guide CVR 30363434[S]. Denmark: IHTSDO,2012.
[5] J A Gallian, S Winters. Modular Arithmetic in the Marketplace[J]. The American Mathematical Monthly,1988,95(6):548-551.
[6] Wagner, Putter. Error Detecting Decimal Digits[J]. CACM,1989, 32(1):106-110.
[7] 成福春,張平,劉華,等.中醫(yī)術(shù)語(yǔ)集制定過(guò)程中關(guān)系的提煉及中醫(yī)術(shù)語(yǔ)服務(wù)平臺(tái)構(gòu)建探討[J].中國(guó)中醫(yī)藥圖書(shū)情報(bào)雜志,2014,38(6):6-10.
Analysis on the Check-digit Algorithm of SNOMED and Its Significance to Traditional Chinese Medicine Terminology
CHENG Fu-chun1, ZHANG Ping2*, LIU Hua1, FANG Min1
(1. Yueyang Hospital of Integrated Traditional Chinese and Western Medicine, Shanghai University of Traditional Chinese Medicine, Shanghai 200437, China; 2. Shuguang Hospital Affiliated to Shanghai University of Traditional Chinese Medicine, Shanghai 201203, China)
This article discussed the advantages and disadvantages of commonly used check-digit algorithms, such as bitwise accumulation module and polynomial multiplication accumulation module. It attached importance to the SNOMED adopting dihedral group D5. Dihedral group D5can test all single bit mistakes and adjacent position bitwise mistakes without adding X, which is a very ideal check-digit algorithm. There does not exist a coding terminology set with the characteristics of information technology or TCM. SNOMED adopted dihedral group D5, which can provide references for TCM terminology coding.
TCM terminology; terminology coding; SNOMED; check-digit algorithm; dihedral group D5
10.3969/j.issn.2095-5707.2015.04.003
上海市衛(wèi)生局科研計(jì)劃課題(2009261)
成福春,副研究員,研究方向?yàn)橹嗅t(yī)信息學(xué)。E-mail: cfc1998cn@126.com
*通訊作者:張平,主治醫(yī)師,研究方向?yàn)橹嗅t(yī)內(nèi)科學(xué)。E-mail: zp1266@126.com
2015-01-05;編輯:魏民)
中國(guó)中醫(yī)藥圖書(shū)情報(bào)雜志2015年4期