JavaScriptで全角/半角判定
=========================

.. note::

   本コンテンツの一部は、業務時間内に調べた内容を含んでおり、株式会社ディー・エヌ・エーの提供でお送りしております。

とある理由で全角、半角の判定が必要になったのですが、簡単技(SJISなどに変換してバイト数計測など)はつかえなかったため、自作する方向で調べて見ました。

Pythonには `unicodedata.east_asian_width() <http://www.python.jp/doc/2.6/library/unicodedata.html#unicodedata.east_asian_width>`_ という関数があり、 `エキスパートPythonプログラミング <http://amzn.to/sBNTjV>`_ というすばらしい書籍の日本語オリジナルの文字コード関連の章によると、この関数が ``"F"`` 、 ``"W"`` 、 ``"A"`` (ただし、Aはフォントにより変わる曖昧な文字)が返すと全角としてカウントすればよい、と書かれています。

こちらを参考にJavaScriptの全角/半角判定を行った幅計算を実装してみます。

まずJavaScriptを知る
--------------------

JavaScriptは内部では、UTF-16という文字コードを使っているそうな。UTFなんとかとか、Unicodeなんとか周りは、UTF-8はASCIIの範囲ならASCIIと互換らしいよ程度しか情報を知らないので、軽く調べてみた。

.. list-table::
   :widths: 5 20

   - * UTF-8
     * 最近よく見る。可変長。BeOSとMac OS XのOS標準。Javaの内部形式はこれ。
   - * UTF-16
     * サロゲート・ペアと呼ばれる機構の範囲だけ可変長。JavaScriptの内部形式。
   - * UTF-32
     * 32ビットでガツンと1文字を表現。4バイト固定。
   - * UCS2
     * UTF-16からサロゲート・ペアを抜いたもの。2バイト固定。
   - * UCS4
     * UTF-32と同じものらしい。4バイト固定。

PythonのUnicodeの内部形式はUCS2かUCS4で、コンパイル時にオプションで設定する。

Pythonのソースを見てみる
------------------------

まずはPythonのライブラリを見て見ました。

.. code-block:: bash

   $ ls ~/Downloads/Python-2.7.2/Lib/ 
   :
   traceback.py
   tty.py
   types.py
   unittest
   urllib.py
   urllib2.py
   urlparse.py
   user.py
   uu.py
   uuid.py
   :

おや、ないぞ？ひょっとしてネイティブなのか？

.. code-block:: bash

   $ ls ~/Downloads/Python-2.7.2/Modules/

   :
   timingmodule.c
   tkappinit.c
   tkinter.h
   unicodedata.c
   unicodedata_db.h
   unicodename_db.h
   xxmodule.c
   xxsubtype.c
   yuv.h
   :

あったあった。さっそく :file:`unicodedata.c` を見てみる。

どうやら、文字コードのDBをみて、FとかAとかの文字を決めているらしい。軽くgrepしてみると、 :file:`unicodedata_d .h` にDBがある模様。このファイルは、unicode.orgにあるファイルを元に、 :file:`Tools/unicode/makeunicodedata.py` というスクリプトを使って自動生成しているとか。

では本家のデータをあたってみる。ファイルは http://www.unicode.org/Public/UNIDATA/EastAsianWidth.txt です。適当に眺めてみると、特に下位ビットがいくつのものが同じ分類みたいな法則性もなさげ。1つおきに違うフラグが設定されているのもある。

ちなみに、unicode.orgにあるUnicode(R)関連のドキュメントやデータファイルはUnicode, Inc/Unicode Consortiumの著作物です。使用にあたっては、 `Unicode.orgのライセンス <http://www.unicode.org/copyright.html>`_ を参照してください。使っているUnicodeのバージョン(6.0以降かその前か)や、ファイルの置き場(Public以下か？)などで適用されるライセンスが異なります。Unicode Character DataBaseは `ここの <http://www.unicode.org/copyright.html#Exhibit1>`_ ライセンスが適用される模様です。Unicodeデータを直接参照しているこのページおよび、このページで作成しているスクリプトは、Unicode(R)に関する著作物表記が必要ですが、それを利用するユーザは必要ないはずです。英語を斜め読みしてなんとなく大意は把握したつもりですが、僕に解釈が違っていればメールください。

それでは :file:`EastAsianWidth.txt` のファイルから全角/半角判定をつくってみようと思います。Pythonで必要な情報を抜いてみます。まずは連続する文字をグループに分けてみます。そんでもって、範囲の先頭だけの配列と、末尾だけの配列に分けました。

.. code-block:: python

   import re
   
   pattern = re.compile(r"([0-9A-F]+)(?:\.\.([0-9A-F]+))?;[FWA]")
   
   start_group = []
   end_group = []
   matched = False
   first = None
   last = None
   
   for line in file("EastAsianWidth.txt"):
       match = pattern.match(line)
       if match:
           if match.group(2):
               start_group.append(int(match.group(1), 16))
               end_group.append(int(match.group(2), 16))
           else:
               code = int(match.group(1), 16)
               last = code
               if not matched:
                   start_group.append(code)
               matched = True
       else:
           if matched:
               end_group.append(last)
               matched = False
   
   for start, end in [
       [0x3400, 0x4DBF], [0x4E00, 0x9FFF], [0xF900, 0xFAFF], [0x20000, 0x2A6DF],
       [0x2A700, 0x2B73F], [0x2B740, 0x2B81F], [0x2F800, 0x2FA1F]]:
           start_group.append(start)
           end_group.append(end)
   
   print sorted(start_group)
   print sorted(end_group)

はい。できました。先頭と末尾を分けたのは、探索をしやすくするためです。もっといいアルゴリズムもあると思うのですが、ぱっと思いついた2分探索法でどこの範囲に入っているかを調べてみます。

2分探索
-------

グループの先頭の配列の中で2分探索し、コードがどこの間に入っているかを調べ、次に同じグループの末尾の情報と比較して範囲内か確認できれば、全角の文字かどうかが分かる！という方針で進めます。

実装してみます。

.. code-block:: javascript

   binary_range_search = function(heads, tails, value) {
       var head = 0;
       var tail = heads.length - 1;
       while (head <= tail) {
           var where = Math.floor((head + tail) / 2);
           if (value == heads[where]) {
               return true;
           } else if (value <  heads[where]) {
               tail = where - 1;
           } else {
               head = where + 1;
           }
       }
       return value <= tails[tail];
   }

サロゲート・ペア対策
--------------------

JavaScriptの文字コードはUTF-16で、unicode.orgから持ってきた情報はUCS-4です。UTF-16からUCS-4に変換する必要があります。とはいっても、ほとんどの文字コードはそのままだし、厳密な判定が不要であれば処理をさぼっても問題ないと思います(ゲームのコードとか)。でもせっかく調べたのでこの機能も入れてみます。id:Constellationさんの `枕を欹てて聴く vs UTF-8, UTF-16, UCS4 <http://d.hatena.ne.jp/Constellation/20110530/1306695104>`_ というエントリーに色々書かれていたので、大いに参考にさせてもらいました。ありがとうございます。

最終的な文字幅探索
------------------

ということでソースコードを紹介します。簡略化するとすれば、サロゲート・ペアの判定を外すのと、探索範囲をUnicodeの厳密な定義ではなく、よく使う文字種に制限すれば早くなる気がします。また、なにも最適化とか考えてないですが、一度探索した文字をキャッシュするなどして、ハッシュで判定する＆ひらがな、カタカナぐらいもキャッシュに入れるなどすればもっと快適になると思います。

.. code-block:: javascript

   var start_group = [
       161, 164, 167, 170, 173, 176, 182, 188, 198, 208, 215, 222, 230, 232, 236, 240, 242, 247, 252, 254, 257, 273, 275,
           283, 294, 299, 305, 312, 319, 324, 328, 333, 338, 358, 363, 462, 464, 466, 468, 470, 472, 474, 476, 593, 609, 708,
           711, 713, 717, 720, 728, 733, 735, 768, 913, 945, 963, 1025, 1040, 1105, 4352, 4515, 4602, 8208, 8211, 8216, 8220,
           8224, 8228, 8240, 8242, 8245, 8251, 8254, 8308, 8319, 8321, 8364, 8451, 8453, 8457, 8467, 8470, 8481, 8486, 8491,
           8531, 8539, 8544, 8560, 8585, 8632, 8658, 8660, 8679, 8704, 8706, 8711, 8715, 8719, 8721, 8725, 8730, 8733, 8739,
           8741, 8743, 8750, 8756, 8764, 8776, 8780, 8786, 8800, 8804, 8810, 8814, 8834, 8838, 8853, 8857, 8869, 8895, 8978,
           9001, 9312, 9451, 9552, 9600, 9618, 9632, 9635, 9650, 9654, 9660, 9664, 9670, 9675, 9678, 9698, 9711, 9733, 9737,
           9742, 9748, 9756, 9758, 9792, 9794, 9824, 9827, 9831, 9836, 9839, 9886, 9918, 9924, 9935, 9955, 9960, 10045, 10071,
           10102, 11093, 11904, 12353, 13312, 13312, 19894, 19968, 19968, 40908, 40960, 43360, 44032, 55216, 57344, 63744, 63744,
           64046, 64110, 64218, 65024, 65072, 65281, 65504, 65533, 110592, 127232, 127280, 127488, 131072, 131072, 173783, 173824,
           173824, 177973, 177984, 177984, 178206, 194560, 194560, 195102, 196608, 917760, 983040, 1048576];
   
   var end_group = [
       161, 164, 168, 170, 174, 180, 186, 191, 198, 208, 216, 225, 230, 234, 237, 240, 243, 250, 252, 254, 257, 273, 275, 283, 295,
       299, 307, 312, 322, 324, 331, 333, 339, 359, 363, 462, 464, 466, 468, 470, 472, 474, 476, 593, 609, 708, 711, 715, 717, 720,
           731, 733, 735, 879, 937, 961, 969, 1025, 1103, 1105, 4447, 4519, 4607, 8208, 8214, 8217, 8221, 8226, 8231, 8240, 8243, 8245,
           8251, 8254, 8308, 8319, 8324, 8364, 8451, 8453, 8457, 8467, 8470, 8482, 8486, 8491, 8532, 8542, 8555, 8569, 8601, 8633, 8658,
           8660, 8679, 8704, 8707, 8712, 8715, 8719, 8721, 8725, 8730, 8736, 8739, 8741, 8748, 8750, 8759, 8765, 8776, 8780, 8786, 8801,
           8807, 8811, 8815, 8835, 8839, 8853, 8857, 8869, 8895, 8978, 9002, 9449, 9547, 9587, 9615, 9621, 9633, 9641, 9651, 9655, 9661,
           9665, 9672, 9675, 9681, 9701, 9711, 9734, 9737, 9743, 9749, 9756, 9758, 9792, 9794, 9825, 9829, 9834, 9837, 9839, 9887, 9919,
           9933, 9953, 9955, 9983, 10045, 10071, 10111, 11097, 12350, 13311, 19893, 19903, 19903, 40907, 40959, 40959, 42182, 43388, 55203,
           55291, 63743, 64047, 64111, 64217, 64255, 64255, 65049, 65131, 65376, 65510, 65533, 110593, 127277, 127386, 127569, 173782,
           173791, 173823, 177972, 177983, 178205, 178207, 194367, 194559, 195101, 195103, 196605, 262141, 917999, 1048573, 1114109];
   
   const kSurrogateBits = 10;
   
   const kHighSurrogateMin = 0xD800;
   const kHighSurrogateMax = 0xDBFF;
   const kHighSurrogateMask = (1 << kSurrogateBits) - 1;
   
   const kLowSurrogateMin = 0xDC00;
   const kLowSurrogateMax = 0xDFFF;
   const kLowSurrogateMask = (1 << kSurrogateBits) - 1;
   
   const kSurrogateMin = kHighSurrogateMin;
   const kSurrogateMax = kLowSurrogateMax;
   const kSurrogateMask = (1 << (kSurrogateBits + 1)) - 1;
   
   const kHighSurrogateOffset = kHighSurrogateMin - (0x10000 >> 10);
   
   binary_range_search = function(heads, tails, value) {
       var head = 0;
       var tail = heads.length - 1;
       while (head <= tail) {
           var where = Math.floor((head + tail) / 2);
           if (value == heads[where]) {
               return true;
           } else if (value <  heads[where]) {
               tail = where - 1;
           } else {
               head = where + 1;
           }
       }
       return value <= tails[tail];
   }
   
   exports.binary_range_search = binary_range_search;
   
   function isHighSurrogate(uc) {
       return ((uc) & ~kHighSurrogateMask) == kHighSurrogateMin;
   }
   
   function isLowSurrogate(uc) {
       return ((uc) & ~kLowSurrogateMask) == kLowSurrogateMin;
   }
   
   function isSurrogate(uc) {
       return ((uc) & ~kSurrogateMask) == kSurrogateMin;
   }
   
   function decodeSurrogatePair(high, low) {
       return ((high & kHighSurrogateMask) << kSurrogateBits) + (low & kLowSurrogateMask) + 0x10000;
   }
   
   exports.east_asian_width = function(text) {
       var width = 0;
       var i;
       for (i=0; i<text.length; ++i) {
           var code = text.charCodeAt(i);
           if(isSurrogate(code)) {
               if (!isHighSurrogate(code)) {
                   throw new Error("UTF-16 decode error");
   
               }
               var low_code = text.charCodeAt(++i);
               if(!isLowSurrogate(low_code)) {
                   throw new Error("UTF-16 decode error");
               }
               code = decodeSurrogatePair(code, low_code)
           }
           if (binary_range_search(start_group, end_group, code)) {
               width += 2;
           } else {
               ++width;
           }
       }
       return width;
   };
   
ついでに、Jasmineのテストコードも貼ってみます。サロゲート・ペアのところはテストサボってますが・・・

.. code-block:: javascript

   var east_asian_width = require("../js/unistr").east_asian_width;
   var binary_range_search = require("../js/unistr").binary_range_search;
   
   describe("East asian character width", function() {
       it ("can count hiragana", function() {
           expect(east_asian_width("こんにちわ")).toEqual(10);
       });
   
       it ("can count kanji", function() {
           expect(east_asian_width("渋川喜規")).toEqual(8);
       });
   
       it ("can count alphabet", function() {
           expect(east_asian_width("abcDEF123!$%")).toEqual(12);
       });
   });
   
   describe("Binary range search", function() {
       it("can match boundary", function() {
           expect(binary_range_search([1], [5], 1)).toBeTruthy();
       });
   
       it("can match in range", function() {
           expect(binary_range_search([1], [5], 2)).toBeTruthy();
       });
   
       it("can match in boundary2", function() {
           expect(binary_range_search([1, 5], [3, 7], 1)).toBeTruthy();
       });
   
       it("can match in boundary3", function() {
           expect(binary_range_search([1, 5], [3, 7], 5)).toBeTruthy();
       });
   
       it("can match in range2", function() {
           expect(binary_range_search([1, 5], [3, 7], 2)).toBeTruthy();
       });
   
       it("can match in range3", function() {
           expect(binary_range_search([1, 5], [3, 7], 6)).toBeTruthy();
       });
   
       it("can match in boundary4", function() {
           expect(binary_range_search([1, 5], [3, 7], 7)).toBeTruthy();
       });
   
       it("can check value is out of range", function() {
           expect(binary_range_search([3], [5], 1)).toBeFalsy();
       });
   
       it("can check value is out of range2", function() {
           expect(binary_range_search([1, 5], [3, 7], 0)).toBeFalsy();
       });
   
       it("can check value is out of range3", function() {
           expect(binary_range_search([1, 5], [3, 7], 4)).toBeFalsy();
       });
   
       it("can check value is out of range4", function() {
           expect(binary_range_search([1, 5], [3, 7], 8)).toBeFalsy();
       });
   });