Goで実現するAho-Corasick法によるNGワード検出アルゴリズム

WRITER: masa
このエントリーをはてなブックマークに追加

はじめに

はじめまして、CyberAgentの26卒内定者として、株式会社QualiArtsで働いている masaです。

本記事では、内定者バイト期間中に実装したNGワード検出アルゴリズムと実装例をご紹介します。

NGワード検出が必要な理由

ゲームにおいて、ニックネームやコメントなど、ユーザーが入力する箇所が多く存在します。その際に、不適切な表現を検知し、入力させないことはコンプライアンス、ユーザー体験に非常に重要です。

要件

開発チームがゲームの設定やデバッグを行う管理画面では、以下2つを設定できるようにします。

  • 拒否リスト
    • NGワードの一覧で、ここにある単語が含まれているとNG
  • 許可リスト
    • 拒否リストに含まれていても、ここに含まれている単語はOK
    • 例: 拒否リストにhoge、許可リストにhogefugaと設定されている場合、hogefugafooはOK

簡単なNGワード検出アルゴリズム

単純に考えると、ワードの検出だけなら以下のように実装できそうです🧐

func (s *service) Validate(text string) error {
    for _, word := range s.ngWordList {
        if strings.Contains(text, word.Text) && word.Type != enum.NgWordType_ALLOW {
            return errors.New("NGワードが含まれています。")
        }
    }

    return nil
}

しかし、この計算量はテキストの長さをn、NGワードの平均長さをm、拒否リストの数をkとすると、最悪でO(n*m*k)になってしまい、パフォーマンスが悪いです。

そのため、高速にNGワードを検出できるAho-Corasick法を利用することで、パフォーマンスの向上を図りました。

Aho-Corasick法とは

Aho-Corasick法は、複数のパターンを同時に検索するためのアルゴリズムです。このアルゴリズムは、文字列検索などにおいて非常に有効です。

Aho-Corasick法は、以下の3つのステップで構成されています。

  1. Trie木の構築: 検索するパターンをTrie木に格納する
  2. 失敗遷移の構築: Trie木の各ノードに失敗遷移を設定する
  3. 検索: 構築したTrie木を使って、テキストを走査し、パターンを検出

Trie木の構築時間はO(m*k)ですが、サーバーの起動時のみ行えばよく、判定を行う際の計算量はO(n)と非常に高速にNGワードを検出できます。

各ステップについて詳しく見ていきます。

Trie木の構築

例えば、拒否リストにmeat, meet, eat, eachの4つの単語があるとします。

この時、Trie木は以下のように構築されます。

trie

失敗遷移の構築

失敗遷移は、Trie木の各ノードに設定される遷移です。これにより、検索中に遷移に失敗した際に、次にどのノードに遷移するかを決定します。

失敗遷移は、照合中の文字列から、接頭語を除く最も長い接尾語を持つノードに遷移します。

例えば、meachという文字列を検索する場合を考えます。

ルートノードからm、e、aと進んだ後、cで失敗します。この時、図の右側のeaに失敗遷移することで、eaの部分をスキップし、eachを検出することができます。

failure

このように、すべてのノードに失敗遷移を設定することで、検索を効率化します。

検索

検索時には、事前に構築したTrie木を使って、テキストを走査します。

走査中に、拒否リストに含まれる単語が見つかった場合、NGワードとして検出します。

実装例

Trie木の構築

初期化時に、拒否リストをTrie木に格納します。

service構造体に、rootNodeを持たせ、ルートから順にTrie木を構築していきます。

type service struct {
    rootNode   *node
    ngWordList []*struct {
        Text string
        Type enum.NgWordType
    }
}

type node struct {
    token       string
    depth       int
    isDenyWord  bool
    isAllowWord bool
    isEnd       bool
    parent      *node
    children    map[string]*node
    failure     *node
}

ノードには、単語の終わりを示すフラグや、親、子ノード、失敗遷移先のノードを持たせます。

for _, word := range s.ngWordList {
    currentNode := s.rootNode
    for char := range strings.SplitSeq(word.Text, "") {
        // 同じ意味の文字列を変換する(e.g. "ア"を"あ"に変換)
        tokens, ok := transformCharacterMap[char]
        if !ok {
            tokens = []string{char}
        }

        for _, token := range tokens {
            nextNode, ok := currentNode.children[token]
            if !ok {
                childNode := newNode(token, currentNode)
                currentNode.children[token] = childNode
                nextNode = childNode
            }

            currentNode = nextNode
        }
    }

    // 単語の終わりに到達した時にフラグを立てておく
    if word.Type == enum.NgWordType_DENY {
        currentNode.isDenyWord = true
        currentNode.isEnd = true
    } else {
        currentNode.isAllowWord = true
        currentNode.isEnd = true
    }
}

失敗遷移の構築

次に、各ノードに対して失敗遷移を構築します。

ns := nodes{s.rootNode}
for n := ns.dequeue(); n != nil; n = ns.dequeue() {
    failureNode := s.rootNode
    if n.depth != 1 {
        var err error
        // ノードの失敗遷移先を取得
        failureNode, err = n.getFailure(n.token)
        if err != nil {
            return err
        }
    }
    n.failure = failureNode

    // 親ノードが拒否リストに含まれるワードの場合は、子ノードも同様にする
    if !n.isEnd {
        if n.parent != nil && (n.parent.isDenyWord || n.parent.isAllowWord) {
            n.isDenyWord = n.parent.isDenyWord
            n.isAllowWord = n.parent.isAllowWord
        } else {
            n.isDenyWord = failureNode.isDenyWord
            n.isAllowWord = failureNode.isAllowWord
        }
    }

    for _, childNode := range n.children {
        ns.enqueue(childNode)
    }
}

失敗遷移先は、再帰的に設定することで、先ほどの図のように、効率的に失敗遷移を構築できます。

func (n *node) getFailure(token string) (*node, error) {
    if n.parent == nil {
        return n, nil
    }
    if n.parent.failure == nil {
        return nil, errors.New("予期せぬtokenです。")
    }
    if childNode, ok := n.parent.failure.children[token]; ok {
        return childNode, nil
    }

    // 再帰的に失敗遷移を取得
    failureNode, err := n.parent.failure.getFailure(n.token)
    if err != nil {
        return nil, err
    }

    return failureNode, nil
}

検索

検索時には、与えられたテキストを1文字ずつ走査し、Trie木を辿っていきます。

拒否リストに含まれる単語が見つかった場合、NGワードとして検出します。

func (s *service) contains(text string) (bool, error) {
    if text == "" {
        return false, nil
    }
    // 入力可能な文字列かどうかをチェック
    if !IsInputText(text) {
        return false, errors.New("不正な文字列です。")
    }

    currentNode := s.rootNode
    isDenyWord := currentNode.isDenyWord
    var isEnd bool

    for char := range strings.SplitSeq(text, "") {
        tokens, ok := transformCharacterMap[char]
        if !ok {
            tokens = []string{char}
        }


        var isNextFailure bool
        for _, token := range tokens {
            // Trie木のリーフノードかどうかのチェック
            isNextFailure = currentNode.isNextFailure(token)
            if isNextFailure && isDenyWord {
                break
            }

            var err error
            currentNode, err = currentNode.next(token)
            if err != nil {
                return false, err
            }
            // 拒否リストに含まれていても、ループが回って許可リストに含まれているものがあればisDenyWordはfalseになる
            if currentNode.isEnd {
                isEnd = true
                isDenyWord = currentNode.isDenyWord
            } else if !isEnd {
                isDenyWord = currentNode.isDenyWord
            }
        }

        if isNextFailure && isDenyWord {
            break
        }
    }

    return isDenyWord, nil
}

まとめ

この記事では、NGワード検出アルゴリズムと実装例について紹介しました。

Aho-Corasick法を使うことで、より高速なNGワード検出が可能になり、ゲームのユーザー体験を向上させることができます。

ABEMA のコンテンツ制作を最適化！ 生成 AI × クラウド映像編集システム / CA.ai #1
次の記事