マルチモードマッチングACアルゴリズムJava(kotlin)実装、中国語モデリング可能

目的
自然言語処理の分野では,テキストで特定の語を検出する場合,これがモードマッチングの問題である.複数の語を検出すると、マルチモードマッチングになります.最も簡単な方法は、与えられたテキストの中ですべての関心のあるモードを順次検出することである.(興味語)このようにすると、興味語が多い場合やテキストが大きい場合に計算の複雑度が高いため、ACアルゴリズムがあり、計算の複雑度が上記の方法に比べてかなり低下する.また、ACアルゴリズムの改善アルゴリズム、例えばACBMなどもあり、本文ではACを重点的に説明する.ネット上でACアルゴリズムに対する博文も少なくないが、大部分はC++プログラムであり、しかもC+プログラムしかない26個の小文字の英字をモデリングし、本明細書のkotlinプログラムは任意のunicode文字をモデリングすることができる.
要点
ACアルゴリズムを理解していない場合は、ブログを見てACマルチモードマッチングアルゴリズムを徹底的に理解してから続行することをお勧めします.MACアルゴリズムの要点は,興味パターンを構築するtrieツリーと,オートマチック失敗ジャンプメカニズムを構築することである.trieツリーを構築するのは理解しやすいが、モードを1つの文字に分け、文字の前後順にツリーでサブノードを生成し、1つのモードが完了するまで.ジャンプに失敗すると、テキストの現在の記号がtrieツリーにサブノードがない場合、続行可能な別のノードが選択され、最悪の場合はルートノードに戻ります.失敗したジャンプメカニズムを構築する場合,ルートノードは他のノードとは異なる.ルートノードがサブノードに一致する場合は、サブノードにジャンプします.そうでない場合は、ルートノードにジャンプします.ルート以外のノードがサブノードに一致している場合は、サブノードにジャンプします.そうでない場合は、失敗したジャンプメカニズムで指定されたノードにジャンプします.
Kotlinプログラム

package com.davezhao.utils

data class Node(
        var finish: Boolean = false,
        var state: Int = 0,
        var pattern: String = ""
) {
    val transTable: MutableMap = mutableMapOf()

    fun containsEdge(edge: Char): Boolean {
        return if (state == 0) true else transTable.contains(edge)
    }

    fun goto(edge: Char): Node {
        return if (state != 0) transTable[edge]!!
        else if (transTable.contains(edge)) transTable[edge]!! else this
    }

    fun addEdge(edge: Char, node: Node): Node {
        transTable.put(edge, node)
        return this
    }
}

class AcPatternMathing {
    val startNode: Node = Node()
    var stateCount = 0
    val correspondingNode: MutableList = mutableListOf(this.startNode)
    lateinit var fail: MutableMap

    fun loadPatterns(patterns: List) {
        var latestState = 1
        patterns.forEach { pattern ->
            var p = this.startNode
            pattern.forEach { symbol ->
                val isExists = p.transTable.contains(symbol)
                p = if (!isExists) {
                    val nextNode = Node(state = latestState++)
                    p.addEdge(symbol, nextNode)
                    this.correspondingNode.add(nextNode)
                    nextNode
                } else {
                    p.goto(symbol)
                }
            }
            p.finish = true
            p.pattern = pattern
        }
        this.stateCount = latestState
    }

    fun dispose() {
        val q = mutableListOf()
        this.fail = mutableMapOf()

        startNode.transTable.forEach {
            fail[it.value.state] = startNode
            q.add(it.value)
        }

        while (!q.isEmpty()) {
            val known = q.removeAt(0)
            known.transTable.forEach { symbol, nxtNode ->
                var p = fail[known.state]
                while (!p!!.containsEdge(symbol)) {
                    println(p.state)
                    p = fail[p.state]
                }
                fail[nxtNode.state] = p.goto(symbol)
                q.add(nxtNode)
            }
        }
    }

    fun match(str: String, S: MutableList) {
        var p = startNode

        var i = 0
        while (i < str.length) {
            val symbol = str[i]
            p = if (p.containsEdge(symbol)) {
                p.goto(symbol)
            } else {
                i--
                fail[p.state]!!
            }
            if (p.finish) {
                S.add(p.pattern)
            }
            i++
        }
    }
}

fun main(args: Array) {
    val ac = AcPatternMathing()
    val patterns = listOf("his", "hers", "she", "he", "  ")
    val matched = mutableListOf()
    ac.loadPatterns(patterns = patterns)
    ac.dispose()

    val str = "hishers        "
    ac.match(str, matched)
    matched.forEach {
        println(it)
    }
}

出力:

his
she
he
hers
  
  
  

参考資料
ACマルチモードマッチングアルゴリズムを徹底的に理解する