Trieを用いた絵文字判定の実装案

[hec12]

絵文字判定の実装案として、Trie ( https://ja.wikipedia.org/wiki/%E3%83%88%E3%83%A9%E3%82%A4%E6%9C%A8 )を用いるのはどうでしょうか?

Trieは文字列の集合を管理するのに適しているデータ構造です。
具体的には、各ノードが文字列の接頭辞を表しており、ノードの関係が木構造となっています。

• 時間面

  • Trieの生成
    Trieの生成の実行時間は 全絵文字のcodePointの合計に比例します。
  • 絵文字の判定
    絵文字判定の最悪実行時間は、絵文字を構成するcodePointの最大個数(現在では7)で抑えられます。

• メモリ面
  Trieのノードの個数は最悪で全絵文字のcodePointの合計個数です。
  しかし、{0x1F469} と {0x1F469, 0x1F3FF, 0x200D 0x1F692} が絵文字である場合は、
  CodePoint の 接頭辞が共通している部分だけノードの個数を減らせるため、 1 つの絵文字につき 1 つの std::vector を用いるよりかはメモリ消費を減らすことが可能だと考えています。

• 拡張面
  木構造で管理しているため、codePoint を構成する個数が変更されてもコードの変更をする必要がないと考えられます。

以下のソースコードは、Trieを用いた絵文字判定の実装例です。
ここでは、木構造の子供の管理にmapを用いています。
注意の欄から絵文字と判断される場合には、最長のcodePointで構成される絵文字にマッチングすると仮定しています。
このソースコードを参考にする場合、「EmojiCodePoints.txt」からcodePointを抽出する部分の実装が甘いので、書き換える必要があると思います。

#include <cstdint>
#include <iostream>
#include <vector>

/* 追加でインクルードしたヘッダファイル */
#include <fstream>
#include <sstream>
#include <map>

class EmojiData
{
private:
    /* データセット (約 2000 種類の絵文字の codePoint 一覧) */
    using Node = struct {
        bool isEmoji = false; /* 絵文字に対応するノードであるかどうか? */
        std::map<uint32_t, size_t> nxt; /* Trieのノード管理 */
    };

    std::vector<Node> trieTree; /* trieTreeを管理する動的配列 */
    const int rootNode = 0; /* 根のノード番号 */
public:

    EmojiData()
    {
        trieTree = {{false, {}}}; // trieTreeの初期化
        const std::string fileName = "EmojiCodePoints.txt";

        std::ifstream readingFile;
        readingFile.open(fileName, std::ios::in);
        std::string bufferString;

        while (!readingFile.eof())
        {
            // read by line
            std::getline(readingFile, bufferString);

            /* </ul> のタグ除去をしています。 (ここのブロックは重要ではないです。)*/
            {
                const size_t bufferLength = bufferString.size();
                if (bufferLength >= 5 and bufferString.substr(bufferLength - 5, 5) == "</ul>")
                {
                    bufferString = bufferString.substr(0, bufferLength - 5); 
                }
            }

            /* 文字列を次のように書き換えています。　{codePoint,...,codePoint}, -> codePoint,...,codePoint */
            {
                const size_t bufferLength = bufferString.size();
                if(bufferLength >= 3 and bufferString[0] =='{' and bufferString[bufferLength-2] =='}' and bufferString[bufferLength-1] ==','){
                    bufferString = bufferString.substr(1, bufferLength - 3); 
                }
            }
            std::istringstream stream(bufferString);
            std::string hexString;
            int currentNode = rootNode; /* 現在のノード番号 */

            /* 根からノードの遷移を行い、たどり着いた先のノードに絵文字であるというフラグを立てます。 */
            while (getline(stream, hexString, ',')) /* stream を ','区切りで hexStringに渡す */
            {
                const uint32_t codePoint = std::stoul(hexString, nullptr, 16); /* hexString を uint32_t に変換 */
                if (trieTree[currentNode].nxt.find(codePoint) == trieTree[currentNode].nxt.end())
                {
                    /* ノードがない場合には新しくノードを生成する */
                    trieTree[currentNode].nxt[codePoint] = trieTree.size();
                    const Node addNode = {false, {}};
                    trieTree.push_back(addNode);
                }
                currentNode = trieTree[currentNode].nxt[codePoint];
            }
            trieTree[currentNode].isEmoji = true;
        }

        return;
    }

    size_t check(auto it, const auto & itEnd)
    {
        size_t emojiLength = 0;
        size_t currentLength = 0;
        size_t currentNode = rootNode; /* 現在のノード番号 */

        while (it != itEnd)
        {
            const std::uint32_t codePoint = *(it++);
            if (trieTree[currentNode].nxt.find(codePoint) == trieTree[currentNode].nxt.end()) {
                /* ノードがない場合は探索を打ち切る。*/
                break;
            }

            /* ノードの遷移と文字列の長さの調整 */
            currentNode = trieTree[currentNode].nxt[codePoint];
            currentLength++;

            if (trieTree[currentNode].isEmoji)
            {
                /* 絵文字が存在するノードの場合、絵文字の長さを更新*/
                /* 複数マッチングする絵文字がある場合には、最長の長さとなる */
                emojiLength = currentLength;
            }
        }

        return emojiLength;
    }
};

int main()
{
    EmojiData emojiData;

    // [入力] 0 個以上の codePoint で表現された文字列
    const std::vector<std::uint32_t> codePoints =
    { 0x30, 0x1F46E, 0x200D, 0x2642, 0x48, 0x1F600, 0x1F800, 0x3042, 0x26CF, 0x30, 0x20E3, 0x1F469, 0x1F469, 0x1F3FF, 0x200D, 0x1F692 };

    auto it = codePoints.begin();

    const auto itEnd = codePoints.end();

    while (it != itEnd)
    {
        const size_t emojiLength = emojiData.check(it, itEnd);

        if (emojiLength == 0) // 非絵文字
        {
            std::cout << "non-emoji: " << std::hex << *(it++) << '\n';
        }
        else // 絵文字
        {
            std::cout << "emoji: {";

            for (size_t i = 0; i < emojiLength; ++i)
            {
                if (i != 0)
                {
                    std::cout << ", ";
                }

                std::cout << std::hex << *(it++);
            }

            std::cout << "}\n";
        }
    }
}

[Reputeless]

ありがとうございます。動作することを確認しました。データセットの余分な </ul> も修正しました。
ファイル読み込みの代わりに、あらかじめソースコードに #include で埋め込むとすっきりしそうです。

EmojiData()
{
    trieTree = { { false,{} } }; // trieTreeの初期化

    const std::vector<std::vector<std::uint32_t>> lines =
    {
        # include "EmojiCodePoints.txt"
    };

    for (const auto& line : lines)
    {
        int currentNode = rootNode; /* 現在のノード番号 */
                                
        /* 根からノードの遷移を行い、たどり着いた先のノードに絵文字であるというフラグを立てます。 */
        for (const auto& codePoint : line)
        {
            if (trieTree[currentNode].nxt.find(codePoint) == trieTree[currentNode].nxt.end())
            {
                /* ノードがない場合には新しくノードを生成する */
                trieTree[currentNode].nxt[codePoint] = trieTree.size();
                const Node addNode = { false,{} };
                trieTree.push_back(addNode);
            }
            currentNode = trieTree[currentNode].nxt[codePoint];
        }

        trieTree[currentNode].isEmoji = true;
    }

    return;
}

実装について、判定速度と拡張性は申し分ないと思いますが、メモリに関しては、Node の std::map 用の内部データの構築のために、単純な std::vector<std::vector<std::uint32_t>> 以上に消費してしまうのが不利だと思います。

sizeof(std::vector) や sizeof(std::map) は通常 16～32 バイトあり、
int32_t 型の要素 1 つを std::vector に追加するとき、メモリ消費はきっかり 4 バイト増えますが、
std::map に追加した場合は常にその数倍以上を消費します。

現状 std::vector<std::vector<std::uint32_t>> はほぼ無駄のない格納形式で、不満としては
・メモリの連続性がない
・各 std::vector ごとに 16～32 バイト分のオーバーヘッドがある
点が気になっているという状況です。

[hec12]

早速、見ていただき、ありがとうございます。
絵文字のcodePointsは #include で読み込めるのですね。

メモリ消費に関しては、指摘されたとおり確かにまだ非効率な点が多いです。
現時点の実装の問題点の改善案としては次のようなことが考えられます。

Trieの木構造のメモリ管理にmapを使う代わりに、木構造の簡潔データ構造であるLOUDSを用いればメモリ使用量を減らすことが可能です[1]。
さらに、LOUDSの効率的な処理のために完備辞書を用いることを考えています。

• 時間面
  Trieの生成の最悪計算量のオーダーは、以前の実装と変わりません。
  絵文字判定の最悪実行時間は、絵文字を構成するcodePointの最大個数をm = 7とすると、O(m log σ) となり、以前の実装と比べてあまり変わらないです。

• メモリ面
  木構造の枝数をl、CodePointの種類 σ = 2^32 とした時に、完備辞書を含めた木構造を管理するためのメモリ使用量は 2l + l log σ + o(l log σ) ビットとなります[1]。

  ここで、lはCodePointsを辞書順で並べ替えた時に、各CodePointsとその直前のCodePointsの異なる個数の総和となります。
  以前のポストのCodePoint の 接頭辞が共通している部分だけノードの個数を減少がこれに対応します。

  以下の場合だと、l = 3 + 3 + 3 + 1 + 2 = 12 となります。
  {0x1F468, 0x200D, 0x2695},
  {0x1F468, 0x1F3FB, 0x200D, 0x1F393},
  {0x1F468, 0x1F3FC, 0x200D, 0x1F393},
  {0x1F468, 0x1F3FC, 0x200D, 0x1F3EB},
  {0x1F469, 0x1F3FE},

  lの値さえ分かれば、メモリを事前に確保できるため、メモリを連続で確保でき、オーバーヘッドを減らすことが可能だと思われます。
  これは、「EmojiCodePoints.txt」を辞書順ソートしておけば、lの計算ができ、さらにはTrieの構築もより高速にできると思われます。

  また、std::vector<std::vector<std::uint32_t>> の場合、CodePointsの数をnとすると、メモリ使用量は n log σ ビットです。

  実装して計測してみないと詳細は分かりませんが、std::vector<std::vector<std::uint32_t>>と比べた場合に、vectorのオーバーヘッドを削減でき、メモリ使用量を抑えることができるかもしれません。

[1] 高速文字列解析の世界―データ圧縮・全文検索・テキストマイニング 岡野原 大輔 (著)

[Reputeless]

詳細な方針の検討をありがとうございます。
LOUDS は初めて知るデータ構造なので調べてみたいと思います。

メモリを一度に連続して確保できるのであれば、多少メモリ消費量が増えても、アクセス効率の観点から std::vector<std::vector<std::uint32_t>> よりも格段に好ましいと考えています。

値を辞書順でソートした codePoint データセットは簡単に用意できるため、元データとして EmojiCodePoints_SortedByValue.txt を追加することにしました。

[hec12]

以前に述べたTrieの簡潔データ構造を実装してみました。

#include <cstdint>
#include <iostream>
#include <vector>

/* 追加でインクルードしたヘッダファイル */
#include <queue>
#include "FID.h"


class EmojiData
{
private:
    FID* trieTree;

    uint32_t* edgeCodePoint;
    size_t edgeCodePointLength = 1; /* 0番ノードに対応する親への辺は存在しないため飛ばす。 */

    uint8_t* isEmoji;
    size_t isEmojiLength = 0;
    size_t isEmojiUint8Length;

    const size_t rootNode = 1;

public:
    ~EmojiData()
    {
        delete trieTree;
        delete[] edgeCodePoint;
        delete[] isEmoji;
    }

    EmojiData()
    {

        const std::vector<std::vector<std::uint32_t>> codePoints =
        {
            #include "EmojiCodePoints_SortedByValue.txt"
        };

        size_t currentNode = rootNode; /* 現在のノード番号 */
        size_t total = 2;

        std::vector<std::vector<uint32_t>> childIdx = {{1}, {}};
        std::vector<std::vector<uint32_t>> childCodePoint = { {0}, {}};
        std::vector<uint8_t> _isEmoji = {'0', '0'};

        {
            std::vector<size_t> parent = {0, 0};
            std::vector<uint32_t> prv = {};

            for (const auto& codePoint : codePoints)
            {
                const size_t prvLength = prv.size();
                const size_t codePointLength = codePoint.size();
                const size_t minLength = std::min<size_t>(prvLength, codePointLength);

                size_t common = 0;
                while (common < minLength and prv[common] == codePoint[common]) common++;

                for (size_t i = 0; i < prvLength - common; ++i)
                {
                    currentNode = parent[currentNode];
                }

                for (size_t i = common; i < codePointLength; ++ i)
                {
                    //printf("%d:%x\n",i,codePoint[i]);
                    parent.emplace_back(currentNode);

                    childIdx[currentNode].emplace_back(total);
                    childIdx.emplace_back(std::vector<uint32_t>());

                    childCodePoint[currentNode].emplace_back(codePoint[i]);
                    childCodePoint.emplace_back(std::vector<uint32_t>());

                    _isEmoji.emplace_back('0');
                    currentNode = total++;
                }

                _isEmoji[currentNode] = '1';
                prv = codePoint;
            }
        }


        {
            /* 木のビット表現 */
            uint8_t* BIT;
            BIT = new uint8_t[2 * total];
            size_t BITLength = 0;

            /* 親への辺に対応するcodePoint */
            edgeCodePoint = new uint32_t[total];
            
            /* ノードが絵文字であるか判定 */
            isEmojiUint8Length = (total + 7) / 8; // ceil(total/8) -> (total+7)/8
            isEmoji = new uint8_t[isEmojiUint8Length];
            
            /* 深さ優先順 から　幅優先順 への 木のインデックスの並び替え */
            std::queue<size_t> q;
            q.push(0);

            while (!q.empty())
            {
                size_t current_idx = q.front();
                q.pop();

                for (size_t i = 0; i < childIdx[current_idx].size(); ++i)
                {
                    BIT[BITLength++] = '1';
                    edgeCodePoint[edgeCodePointLength++] = childCodePoint[current_idx][i];
                    q.push(childIdx[current_idx][i]);
                }
                BIT[BITLength++] = '0';

                const size_t upperPos = isEmojiLength >> 3;
                const size_t lowerPos = isEmojiLength & 0x07;
                const uint8_t lowerPosMask = (1 << (7 - lowerPos));
                isEmojiLength++;

                if (_isEmoji[current_idx] == '1')
                {
                    isEmoji[upperPos] |= lowerPosMask;
                }
                else
                {
                    isEmoji[upperPos] &= ~lowerPosMask;
                }
            }

            BIT[BITLength++] = '\0';
            trieTree = new FID(BIT);
            delete [] BIT;
        }

        return;
    }

    size_t check(auto it, const auto & itEnd)
    {
        size_t emojiLength = 0;
        size_t currentLength = 0;
        size_t currentNode = rootNode; /* 現在のノード番号 */

        while (it != itEnd)
        {
            const std::uint32_t codePoint = *(it++);

            const size_t from = trieTree->select(currentNode - 1 , 0) + 1;
            const size_t to = trieTree->select(currentNode + 1 - 1, 0);

            /* ノードがない場合は探索を打ち切る。*/
            if (from == to) break;

            /* BinarySearchを追記する。*/

            uint16_t lower = from, upper = to;
            while (upper - lower > 1)
            {
                const uint16_t mid = (lower + upper) / 2;
                //printf("%d:%x %x\n",trieTree->rank(mid, 1),edgeCodePoint[trieTree->rank(mid, 1)],codePoint);
                if (edgeCodePoint[trieTree->rank(mid + 1, 1)] <= codePoint)
                {
                    lower = mid;
                }
                else
                {
                    upper = mid;
                }
            }

            /* ノードが見つからない場合も探索を打ち切る */
            
            if (edgeCodePoint[trieTree->rank(lower + 1, 1)] != codePoint) break;

            /* ノードの遷移と文字列の長さの調整 */
            currentNode = trieTree->rank(lower + 1, 1);
            currentLength++;

            const size_t upperPos = currentNode >> 3;
            const size_t lowerPos = currentNode & 0x07;
            const uint8_t lowerPosMask = (1 << (7 - lowerPos));

            if (isEmoji[upperPos] & lowerPosMask)
            {
                /* 絵文字が存在するノードの場合、絵文字の長さを更新*/
                /* 複数マッチングする絵文字がある場合には、最長の長さとなる */
                emojiLength = currentLength;
            }
        }

        return emojiLength;
    }
};


int main()
{
    EmojiData emojiData;

    // [入力] 0 個以上の codePoint で表現された文字列
    const std::vector<std::uint32_t> codePoints =
    { 0x30, 0x1F46E, 0x200D, 0x2642, 0x48, 0x1F600, 0x1F800, 0x3042, 0x26CF, 0x30, 0x20E3, 0x1F469, 0x1F469, 0x1F3FF, 0x200D, 0x1F692 };

    auto it = codePoints.begin();

    const auto itEnd = codePoints.end();

    while (it != itEnd)
    {
        const size_t emojiLength = emojiData.check(it, itEnd);

        if (emojiLength == 0) // 非絵文字
        {
            std::cout << "non-emoji: " << std::hex << *(it++) << '\n';
        }
        else // 絵文字
        {
            std::cout << "emoji: {";

            for (size_t i = 0; i < emojiLength; ++i)
            {
                if (i != 0)
                {
                    std::cout << ", ";
                }

                std::cout << std::hex << *(it++);
            }

            std::cout << "}\n";
        }
    }
}

完備辞書(FID)も1ファイルにまとめると、長くなるのでクラス化してファイルを分けました。
以下のレポジトリから使えます。
https://github.com/hec12/FID

コンストラクタを走らせた後 のEmojiData クラスのメモリ使用量を比較しました。

• 上記の実装

• const std::vector<std::vector<std::uint32_t>> codePoints を EmojiData クラスに持たせた場合

class EmojiData
{
private:
    std::vector<std::vector<std::uint32_t>> codePoints;
public:
    ~EmojiData()
    {
    
    }

    EmojiData()
    {

        codePoints =
        {
            #include "EmojiCodePoints_SortedByValue.txt"
        };
    }
};

• メモリ使用量の測定方法
  main関数の部分を以下のように置き換えて

int main(void)
{
	EmojiData emojiData;
	while(1){}
	return 0;
}

実行中のプロセスを cat /proc/*/status として、 データセグメントにあたる VmData の容量で計測

• 測定結果
  • const std::vector<std::vector<std::uint32_t>> codePoints 400 KB
  • 簡潔データ構造を用いたTrie　272 KB

この実装では、「EmojiCodePoints_SortedByValue.txt」を差し替えるだけでコードの変更をする必要はないです。

EmojiData クラスのコンストラクタで、「"EmojiCodePoints_SortedByValue.txt"」を読み込んでいるのでメモリ使用量のピークは大きいです。
しかし、「EmojiCodePoints_SortedByValue.txt」を逐次読み込みしたり、文字列を用いずにFIDの初期化を行えば、メモリ使用量のピークはもう少しは減せると思います。

[Reputeless]

実装と検証をありがとうございます。追ってこちらでも検証させていただきます。
FID のリポジトリに関してはライセンス (MIT or Apache を推奨します) を記載していただけると、今後必要な際に参照できるため幸いです。

[hec12]

FIDのリポジトリにMITライセンスを記載しました。

[Reputeless]

ありがとうございます。

[Reputeless]

ご提案いただいた #1 と #2 を検証のため OpenSiv3D v0.1.6 以降に実装します。
最終的にどちらを使用するかは今後判断させていただきます。
追って経過を報告するため、Close せず残しておきます。