C
UTF-8
ICU
unicode

ICUを使ったUTF-8文字列の検索

以下のエントリの続編で、ICU(International Components for Unicode)を利用して文字列を検索するプログラムを作ってみます。
ICUでUTF-8の文字列を1文字ごとに分割する - Qiita

UStringSearch(usearch.h)を使った文字列検索

ICUにはイテレータ的に文字列を検索するための機能が提供されています。UStringSearchは、UString文字列中から、指定されたパターン文字列を検索して、その位置やマッチした長さなどを返します。

検索に使用されるアルゴリズムはBoyer-Moore法です。また、マッチングの際の等価性としては正準等価と互換等価のそれぞれをサポートしており、デフォルトは後者だそうです。Unicodeの等価性については、Wikipediaの解説を参照してください。

次のコードは、UStringSearchを使って文字列検索を行うプログラムの例です。

text_search.c
#include <stdio.h>
#include <unicode/ustring.h>
#include <unicode/usearch.h>

int text_search(const char *text, const char *pattern) 
{
    int32_t length = -1;                    // 文字列のサイズ、NULL終端文字列の場合は-1
    UErrorCode errorCode = U_ZERO_ERROR;    // エラーコード
    const char *locale = uloc_getDefault(); // ロケール

    // 対象テキストのUStringの生成
    UChar utext[128];
    int32_t utextCapacity = 128;
    int32_t utextLength;
    u_strFromUTF8(utext, utextCapacity, &utextLength, text, length, &errorCode);

    // パターンのUStringの生成
    UChar upattern[16];
    int32_t upatternCapacity = 16;
    int32_t upatternLength;
    u_strFromUTF8(upattern, upatternCapacity, &upatternLength, pattern, length, &errorCode);

    // UStringSearchの生成
    UStringSearch *search = usearch_open(upattern, length, utext, length, locale, NULL, &errorCode);

    /* UBreakIteratorを明示的に指定する場合の例
    // イテレータの生成
    UBreakIterator *iterator = ubrk_open(UBRK_CHARACTER, locale, NULL, 0, &errorCode);
    UText *utext_utf8 = utext_openUTF8(NULL, text, length, &errorCode);
    ubrk_setUText(iterator, utext_utf8, &errorCode);
    // UStringSearchの生成
    UStringSearch *search = usearch_open(upattern, -1, utext, -1, locale, iterator, &errorCode);
    */

    // UStringSearchの生成失敗
    if (U_FAILURE(errorCode)) {
        fprintf(stderr, "UStringSearch couldn't be opened.\n");
        return -1;
    }

    // 検索実行
    int position = usearch_first(search, &errorCode);
    while (U_SUCCESS(errorCode) && position != USEARCH_DONE) {
        int matchLebgth = usearch_getMatchedLength(search);
        printf("Detected at %d, length is %d.\n", position, matchLebgth);
        position = usearch_next(search, &errorCode);
    }

    // パターンが見つからなかった
    if (U_FAILURE(errorCode)) {
        fprintf(stderr, "Couldn't detect the keyword.\n");
    }

    usearch_close(search);

    return 0;
}

int main(void)
{
    const char *text = "あいうえおポプテピピックさしすせそポプテピピックたちつてとポプポプテピピックなにぬねの"; 
    // 1つ目と3つ目のポプテピピックはコードポイント数7
    // 2つ目のポプテピピックはコードポイント数11

    const char *pattern = "ポプテピピック";     // コードポイント数7
    text_search(text, pattern);
}

サンプルコードの解説

実際に検索を実行するのはUStringSearchオブジェクトです。これはusearch.hに宣言されており、同じくusearch.hにあるusearch_open()関数で生成することができます。usearch_open()には検索対象の文字列とパターン文字列を渡しますが、どちらもchar*ではなくUString文字列(UChar*)として渡さなければいけません。

そこで、まず対象文字列とパターン文字列をu_strFromUTF8()を使ってUString化し、その上で出来たUStringを使ってusearch_open()を呼び出します。

// UStringSearchの生成
UStringSearch *search = usearch_open(upattern, length, utext, length, locale, NULL, &errorCode);

usearch_open()の引数は以下の通りです。
- 第1引数: パターン文字列
- 第2引数: パターン文字列の長さ(NULL終端文字列の場合は-1)
- 第3引数: 対象文字列
- 第4引数: 対象文字列の長さ(NULL終端文字列の場合は-1)
- 第5引数: ロケール
- 第6引数: BreakIterator
- 第7引数: エラーコードの格納先

BreakIteratorはNULLを指定して省略することもできます。マッチングの際に任意のBreakIteratorを使いたい場合には、ここで指定するか、後からusearch_setBreakIterator()を使ってセットします。

実際の検索は、usearch_first()やusearch_next()といった関数で行います。

// 検索実行
int position = usearch_first(search, &errorCode);
while (U_SUCCESS(errorCode) && position != USEARCH_DONE) {
    int matchLebgth = usearch_getMatchedLength(search);
    printf("Detected at %d, length is %d.\n", position, matchLebgth);
    position = usearch_next(search, &errorCode);
}

usearch_first()は先頭から調べて最初にマッチした位置を返します。マッチすると、UStringSearchの内部のポインタが、マッチした位置に移動します。usearch_next()は、現在のポインタから調べて、次にマッチした位置を返します。これらの関数は、検索が対象文字列の最後まで到達した場合にはUSEARCH_DONEを返します。

usearch_getMatchedLength()を使うと、最後にマッチした文字列の長さを調べることができます。U_SUCCESS()はutypes.hに定義されている関数で、エラーコードを渡して、それがエラーであることを示しているか否かを調べます。

検索が完了したら、usearch_close()でUStringSearchオブエクトを解放しておきましょう。

コンパイルと実行

usearch.hを使う場合、コンパイル時にicuucに加えてicui18nもリンクする必要があります。

$ cc -licuuc -licui18n text_search.c -o text_search
$ ./text_search
Detected at 5, length is 7.
Detected at 17, length is 11.
Detected at 35, length is 7.

このプログラムの場合、パターン文字列"ポプテピピック"は対象文字列の中に3回登場します。そのうち2つ目のものは複数のコードポイントからなる書記素を含んでいるので厳密なビットの並びはパターン文字列と異なりますが、ちゃんと等価とみなされていることがわかります。