成福春，張平，劉華，房敏

1.上海中醫(yī)藥大學附屬岳陽中西醫(yī)結(jié)合醫(yī)院，上海 200437；2.上海中醫(yī)藥大學附屬曙光醫(yī)院，上海 201203

SNOMED編碼校驗位算法解析及其對中醫(yī)術語編碼的意義

成福春1，張平2*，劉華1，房敏1

1.上海中醫(yī)藥大學附屬岳陽中西醫(yī)結(jié)合醫(yī)院，上海 200437；2.上海中醫(yī)藥大學附屬曙光醫(yī)院，上海 201203

本文討論了編碼之中常用到的按位累加取模、多項式乘法累加取模等校驗位算法的優(yōu)缺點，尤其是對系統(tǒng)化醫(yī)學術語集（SNOMED）編碼采用二面體群D5校驗位算法作了較深入的討論。二面體群D5算法不僅可以校驗出所有一位錯誤及相鄰位置換位錯誤，而且不需要增加字母 X，是一種非常理想的校驗位算法。國內(nèi)目前尚無一套既具有信息技術特征，又具有中醫(yī)學科本身特征的編碼化的術語集，SNOMED編碼采用二面體群D5校驗位算法，對于中醫(yī)術語編碼具有重要的借鑒意義。

中醫(yī)術語；術語編碼；系統(tǒng)化醫(yī)學術語集；校驗位算法；二面體群D5

醫(yī)學術語及其編碼化，對于規(guī)范臨床數(shù)據(jù)采集，數(shù)據(jù)檢索分析利用、提升醫(yī)療質(zhì)量以及研究的深度，具有重要意義[1]。系統(tǒng)化醫(yī)學術語集-臨床術語（ systematized nomenclature of medicineclinical terms, SNOMED CT）通過編碼進行世界范圍內(nèi)的統(tǒng)一術語交流，即代碼唯一，或稱概念唯一。但是代碼所代表的內(nèi)容其形式可以多樣，如英文形式、中文形式或者各國語言形式。通過定義代碼與代碼之間的關系，來體現(xiàn)學科本身的邏輯與語義。

1 系統(tǒng)化醫(yī)學術語集-臨床術語編碼簡介

在SNOMED CT術語體系中，賦予每一個特定術語一個代碼，即擴展版的SNOMED CT概念標識符（SCTID字段）。代碼本身不要求有特別的含義，只是代表這個術語本身，利于計算機處理。

在代碼結(jié)構(gòu)中，具有相關的屬性信息，如extension item identifier（擴展項目標識符），共8位，代表具體的項目編碼；namespace identifier（名稱空間標識符），共7位，代表維護代碼的機構(gòu)；partition identifier（部分標識符），2位，10代替概念，20代表描述，30代表關系；最后一位是check-digit（校驗位），便于計算機自動糾錯。SNOMED通過3張表來體現(xiàn)，即概念表、定義表、關系表。SCTID是概念表中的最重要的字段。目前擴展版的SCTID字段結(jié)構(gòu)如圖1。

圖1 擴展版的SCTlD數(shù)字編碼結(jié)構(gòu)

雖然用戶可能很少手工錄入SCTID，但是還是有可能會發(fā)生這種情況。在手工錄入過程中，由于數(shù)字串太長，不可避免地會發(fā)生數(shù)據(jù)錄入錯誤。而通過校驗位，能夠大大減少數(shù)據(jù)錄入錯誤。

J Verhoeff[2]基于對手工錄入時發(fā)生的 12 000個錯誤的研究，將人們常犯的錯誤進行總結(jié)，共分為7類。⑴單個錯誤，a變成b，在所有錯誤中約占60%～95%。⑵遺漏或增加 1個數(shù)字，占所有錯誤的 10%～20%。⑶換位錯誤，ab變成ba，占所有錯誤的10%～20%。⑷雙子錯誤，如aa變成bb，占所有錯誤的0.5%～1.5%。⑸跳躍轉(zhuǎn)換，如acb變成bca，占所有錯誤的0.5%～1.5%。⑹跳躍雙子錯誤，如aca變成bcb，發(fā)生率＜1%。⑺發(fā)音錯誤，如1a與a0，英文的13與30、14與40、15與50等，發(fā)生率約0.5%。

可以看出，人們在處理數(shù)字錯誤時，常犯的錯誤以一位為主。因此，考慮增加校驗位，針對一位錯誤，設計相應的算法，成為校驗位研究的主要內(nèi)容。

2 常見校驗位算法的優(yōu)缺點

2.1 按位累加取模

常見的模（除數(shù)）為7、9、11、13等質(zhì)數(shù)，因其每一位余數(shù)均與該?；ベ|(zhì)。按位累加取模，賦予校驗位。在驗證時，按同樣算法進行比較，相等說明編碼正確，不等則編碼有誤。

優(yōu)點是算法簡單，可以校驗出大部分一位錯誤。缺點是累加取模，無位置信息，不能判斷出相鄰轉(zhuǎn)換錯誤，如ab變成ba。當模的數(shù)字＜10時，會出現(xiàn)相關重復錯誤情況，導致不能檢測出所有單個錯誤，如取模為 7 的7與0、8與1、9與2，取模為9的9與0等。

2.2 多項式乘法校驗位算法

原理為 K元組的點乘和取余，即（a1，a2……ak）·(w1，w2……wk) mod m＝(a1w1＋a2w2＋……akwk) mod m＝0。常見的模m為10或11。

2.2.1 取模m為10 UPC編碼（universal product code）是最早大規(guī)模應用的條碼，為長度固定、連續(xù)性的條碼，主要在美國和加拿大使用，由于其應用范圍廣泛，故又被稱為萬用條碼。UPC編碼僅可用來表示數(shù)字，故其字碼集為數(shù)字0～9。在UPC編碼中，a1、a2……a12滿足以下等式：（a1，a2,……,a12）·（3，1，3，1……3，1） mod 10＝0，a12為校驗位值。

優(yōu)點是可以檢測出所有的單個錯誤，也可以檢測出ab變成ba這種相鄰位置換位錯誤。缺點是不能檢測出abc變成cba這種錯誤，也不能檢測出|a-b|＝5的交換錯誤[3]。

2.2.2 取模m為11 模為11時，余數(shù)為0，1，2，3，4，5，6，7，8，9，10。當余數(shù)為10時，為了不增加位數(shù)，往往用X來代替。如國際圖書編碼ISBN 號0-669-19493，校驗位X，代表10，校驗位a10滿足（a1，a2,……,a9，a10）·（10，9，8，7，6，5，4，3，2，1）mod 11＝0。

優(yōu)點是可以檢測出所有一位錯誤及相鄰位置換位錯誤。缺點是增加了字母X，使編碼不再是純數(shù)字，在信息系統(tǒng)定義數(shù)據(jù)類型方面存在不便。由于在計算機表示中，數(shù)字的表示與字母的表示存在著差別，將兩者合在一起來表示某一特定的編碼，無疑增加了算法處理的復雜性，增加了系統(tǒng)設計及改造的成本，增加了系統(tǒng)處理的難度以及社會使用成本。

我國的身份證校驗位算法即使用上述算法。根據(jù)中華人民共和國國家標準GB 11643－1999中有關公民身份號碼的規(guī)定，公民身份號碼是特征組合碼，由17位數(shù)字本體碼和1位數(shù)字校驗碼組成。排列順序從左至右依次為6位數(shù)字地址碼、8位數(shù)字出生日期碼、3位數(shù)字順序碼和1位數(shù)字校驗碼。校驗位根據(jù)前面17位數(shù)字碼，按照ISO 7064:1983.MOD 11-2編碼規(guī)則∑（ai×wi）mod 11計算。其中，i表示號碼字符從右至左包括校驗碼在內(nèi)的位置序號；ai表示第i位置上的號碼字符值；wi表示第i位置上的加權因子，其數(shù)值依據(jù)公式是wi＝2（i－1）mod 11。

以某男性公民身份證號碼為例，其本體碼為34052419800101001，按照上述公式計算，見表1。

根據(jù)計算結(jié)果，從表2中查出，計算結(jié)果為2的校驗碼為 X，所以該男性公民身份證號碼應該為34052419800101001X。

表1 某男性公民身份證校驗位算法表

表2 身份證取模m為11的余數(shù)與校驗碼對照表

3 二面體群D5算法思想及其在SCTlD中的應用

法國天才數(shù)學家伽羅瓦于1822年首次提出“群”的概念，目的是解決高次方程有無定解以及解的表示問題。如一個正四邊形，其旋轉(zhuǎn)90°、180°、270°、360°，形狀仍與原來的形狀重合；而其左右對角線、水平及垂直平分線均反射對稱。抽象出來，具有旋轉(zhuǎn)對稱與反射對稱的正n邊形，稱為二面體。旋轉(zhuǎn)與對稱被稱為二元運算中的元素。它的各種變換可以由置換群來表示，其相應的變換迭加后得到的元素仍在群中。群是抽象代數(shù)研究的最主要內(nèi)容。這種不再以單純的數(shù)字的加減，而以數(shù)據(jù)的結(jié)構(gòu)為主要的研究內(nèi)容，是抽象代數(shù)的一個本質(zhì)特征。

二面體群 D5，以正五邊形為例，考慮其旋轉(zhuǎn)對稱，將360°分為5份，則分別是72°、144°、216°、288°、360°（或 0°）。而對稱變換，則以某一個頂點作垂直于頂點所對的邊的垂直平分線。這時，會發(fā)生頂點相關位置的交換。

對此作Calay（凱萊）乘法表，0代表旋轉(zhuǎn)0° 或360°，1代表旋轉(zhuǎn)72°，2代表旋轉(zhuǎn)144°，3代表旋轉(zhuǎn)216°，4代表旋轉(zhuǎn)288°，5代表以正五邊形的頂點A作反射對稱變換，6代表以正五邊形的頂點B作反射對稱變換，以此類推。表中的具體數(shù)值是某兩個變換疊加的結(jié)果（兩個元素相乘），在二面體群D5乘法表中（見表3），3與6的相乘，結(jié)果為9，表示正五邊形的起始狀態(tài)，經(jīng)過旋轉(zhuǎn)216°，再以A點作對稱變換，其結(jié)果與起始位置直接作 E點對稱變換，結(jié)果是一樣的。如此則可以完全表示出二面體群D5的變化規(guī)律。其各種復雜的變化規(guī)律都是以上基礎規(guī)律的迭加。因此，可以利用連續(xù)變換的方法，得出最終的一個狀態(tài)。

J Verhoeff于1969年開發(fā)出了基于二面體群D5的校驗位算法?？紤]數(shù)字串a(chǎn)1a2……an-1，增加1位校驗位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）。所有的單個數(shù)字錯誤均被檢出。這里，σ代表某種置換，*代表二面體群D5乘法運算。二面體群D5乘法表見表3。

表3 二面體群D5乘法表

又由于，如果a≠b，a*σ（b）≠b*σ（a），可以推出σi（a）*σ（i＋1）（b）≠σi（b）*σ（i＋1）（a），因此，所有的包括相鄰位置的交換錯誤均被檢出。

表4為變換如σ=（01589427）（36）形成的置換表。

SNOMED CT中的SCTID，即采用了二面體群D5算法進行校驗[4]。如 SNOMED CT（RF1）中的代碼138875005，代表SNOMED CT Concept，其最后的“5”是校驗位，是根據(jù)前面8個數(shù)字，通過二面體D5校驗位算法得出的數(shù)值。

首先，設 a0為校驗位，將數(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

從右邊開始計算，

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

表4 置換表σ=（01589427）（36）

J Verhoeff的校驗捕獲了所有的單個錯誤、所有的相鄰交換錯誤、＞95%的雙子錯誤、＞94%的跳躍轉(zhuǎn)換與跳躍雙子錯誤，及大多數(shù)的元音錯誤。因此，與mod 11一樣，減少校驗錯誤至2%～3%，但是不需要增加X[5-6]。

4 對于中醫(yī)術語編碼的意義

編碼的目的在于應用，在于方便地被計算機處理。通過校驗位算法，不僅可以判斷是否存在輸入錯誤，也可以判斷是否是有效的編碼，從而提高實際應用的準確性。代碼的準確性是代碼應用的基礎，而校驗位對于代碼錄入準確性的提高，起到了重要的作用。從而使后續(xù)基于代碼的若干應用成為可能。與條形碼、二維碼等結(jié)合起來，便捷地進行數(shù)據(jù)錄入，可順暢地實現(xiàn)信息化的各種流程。

在實際進行中醫(yī)術語編碼過程中，可以考慮按機構(gòu)、分類、序號進行編碼，通過算法產(chǎn)生完整編碼并發(fā)布。而對于中醫(yī)術語服務平臺而言，可以提供編碼服務、編碼校驗服務等相關功能[7]。

準確而統(tǒng)一的編碼也是知識庫構(gòu)建的基礎，知識庫的構(gòu)建依賴于無歧義的編碼。如某一個診斷，可能是某幾個癥狀的集合，體現(xiàn)為某一個編碼可以分解為另外幾個編碼的集合。

曾有觀點認為，中醫(yī)本質(zhì)上是術語，術語規(guī)范了，中醫(yī)也就規(guī)范了。這句話可能不夠全面，但是有著很深的道理。對于任何一門學科而言，都可以理解為本質(zhì)上是數(shù)據(jù)，數(shù)據(jù)規(guī)范了，學科本身也就規(guī)范了。而對于計算機而言，更有意義的是基于術語的編碼，以及編碼與編碼之間的關系。

縱觀中醫(yī)發(fā)展史，數(shù)學內(nèi)容較少，這也是中醫(yī)發(fā)展步伐較慢的根本原因。不能從相關數(shù)據(jù)中獲取得到模型，不能進行有效的驗證，不能摒棄錯誤或不正確的理論，發(fā)展就會緩慢，這主要是受當時的環(huán)境條件所限。但是，如今到了信息社會，網(wǎng)絡高度發(fā)達，可以進行大規(guī)模的數(shù)據(jù)采集與分析，進行群體研究，從宏觀療效到微觀機制更加深入地研究，這些為中醫(yī)的現(xiàn)代化以及中醫(yī)自身的進步與突破提供了可能。對于計算機而言，體現(xiàn)數(shù)據(jù)質(zhì)量與效率之處，莫過于中醫(yī)自身規(guī)范而統(tǒng)一的術語編碼體系。

5 討論

二面體群D5以其具有全反對稱映射的10個數(shù)字最小組合，在數(shù)字編碼中具有重要意義。而校驗位的另一個重要作用是具有防偽功能，如信用卡號的3個校驗位，以及部分國家的紙幣編碼。

目前，國內(nèi)尚無一套既具有信息技術特征，又具有中醫(yī)學科本身特征的醫(yī)學術語集。而其中的編碼，是中醫(yī)術語集制定過程中的重要內(nèi)容。二面體群 D5校驗位算法，是SNOMED編碼所采用的算法，對中醫(yī)術語集體系結(jié)構(gòu)的制定具有非常重要的借鑒意義。

但是，要對其進行深入研究，需要解決以下3個問題。

第一，σ=（01589427）（36）如何產(chǎn)生，有無其他的置換序列。回答這個問題，需要理解全反對稱映射這個概念，即如果a≠b，a*σ（b）≠b*σ（a）。筆者通過設計相應算法，找到了34 040個全反對稱映射，0～9這10個數(shù)字的全排列10!為3 628 800，34 040個全反對稱映射占其 0.938%。如（01572）（496），（0284316）,(0519324678),(1932758)（46）等。這使得中醫(yī)術語的編碼可以不再局限于已有的SNOMED編碼置換序列。

第二，如何產(chǎn)生出字母與數(shù)字組合的校驗位算法。二面體群 D18可以解決英文字符與數(shù)字混合的校驗位編碼問題，但需要對其全反對稱序列查找設計相應的算法。

第三，變換序列的分類以及校驗準確度的評估問題。針對前文中提到的常犯的7類錯誤，需要對每一類變換能夠解決各種錯誤的錯誤率進行分析。

而對于一位數(shù)字的糾錯，可以采用兩位校驗位算法，不僅可以確定一位數(shù)字的錄入錯誤，而且可以確定是哪一個位置發(fā)生錯誤，從而可自動糾正一位數(shù)字錯誤。這些問題，都是后續(xù)研究的重要內(nèi)容。

[1] 成福春,劉華,房敏.基于 SNOMED術語編碼兩節(jié)點之間多路徑算法的實現(xiàn)及其對中醫(yī)術語編碼的意義[J].中國中醫(yī)藥圖書情報雜志,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ī)術語集制定過程中關系的提煉及中醫(yī)術語服務平臺構(gòu)建探討[J].中國中醫(yī)藥圖書情報雜志,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)生局科研計劃課題（2009261）

成福春，副研究員，研究方向為中醫(yī)信息學。E-mail: cfc1998cn@126.com

*通訊作者：張平，主治醫(yī)師，研究方向為中醫(yī)內(nèi)科學。E-mail: zp1266@126.com

2015-01-05；編輯：魏民）