Java-версия JieBa, сегментация слов, исходный код, ходьба

Java задняя часть алгоритм Jieba

JieBa использует

List<SegToken> process = segmenter.process("今天早上，出门的的时候，天气很好", JiebaSegmenter.SegMode.INDEX);
for (SegToken token:process){
    //分词的结果
    System.out.println( token.word);
}

Вывод выглядит следующим образом

今天
早上
，
出门
的
的
时候
，
天气
很
好

Логика выполнения сегментации слов

Видно, что ядро

  1. содержит словарь внутри
  2. логика причастий
  3. Детализация сегментации различных режимов

образец причастия

  • поиск точно сокращает, используется для сегментации слов пользовательского запроса
  • индексировать повторно сегментировать длинные слова, чтобы улучшить скорость отзыва

процесс сегментации слов

Видно, что ядро

  1. Создать DAG из ввода
  2. выбрать высокочастотные слова
  3. Если оно не включено в словарь, то есть слово не записано, провести повторную идентификацию

Создать группу обеспечения доступности баз данных

  1. Получить загруженную попытку
  2. Соответствие из дерева дерева, основной код выглядит следующим образом
    int N = chars.length; //获取整个句子的长度
int i = 0, j = 0; //i 表示词的开始 ；j 表示词的结束
while (i < N) {
    Hit hit = trie.match(chars, i, j - i + 1); //从trie树中匹配
    if (hit.isPrefix() || hit.isMatch()) {
        if (hit.isMatch()) {
            //完全匹配
            if (!dag.containsKey(i)) {
                List<Integer> value = new ArrayList<Integer>();
                dag.put(i, value);
                value.add(j); 
            }
            else
                dag.get(i).add(j); //以当前字符开头的词有哪些，词结尾的坐标记下来
        }
        j += 1; 
        if (j >= N) {
            //以当前字符开头的所有词已经匹配完成，再以当前字符的下一个字符开头寻找词
            i += 1;
            j = i;
        }
    }
    else {
    //以当前字符开头的词已经全部匹配完成，再以当前字符的下一个字符开头寻找词
        i += 1;
        j = i;
    }
}
  3. Дополнительные символы в предложениях, которых нет в DAG

Результаты выборки DAG

Например, введите "сегодня утром"

Его дисплей DAG выглядит следующим образом
То есть в предложении «сегодня утром» слова, которые можно найти в трее, это

今/今天/早/早上/上

Приложение Trie Tree

JieBa внутренне хранит файл dict.txt, например записьX光线 3 n. Древовидная структура внутреннего хранилища Trie

  • nodeState: Текущее состояние DictSegment, по умолчанию 0, 1 означает, что путь от корневого узла к текущему узлу означает слово, такое как рентген и рентген

  • storeSize: количество сегментов, хранимых текущим узлом.

Например, кроме рентгена есть рентгеновские лучи.

  • childrenArray и childrenMap используются для хранения дочерних узлов дерева дерева.

storeSize ARRAY_LENGTH_LIMIT, использовать хранилище карты, значение равно 3

выбрать высокочастотные слова

Основной код выглядит следующим образом

 for (int i = N - 1; i > -1; i--) {
 //从右往左去查看句子,这是因为中文的重点一般在后面
 //表示词的开始位置
        Pair<Integer> candidate = null;
        for (Integer x : dag.get(i)) {
        //x表示词的结束位置
        // wordDict.getFreq表示获取trie这个词的频率
        //route.get(x+1)表示当前词的后一个词的概率
        //由于频率本身存储的是数学上log计算后的值，这里的加法其实就是当前这个词为A并且后面紧跟着的词为B的概率，B已经由前面算出
            double freq = wordDict.getFreq(sentence.substring(i, x + 1)) + route.get(x + 1).freq;
            if (null == candidate) {
                candidate = new Pair<Integer>(x, freq);
            }
            else if (candidate.freq < freq) {
                //保存概率高的词
                candidate.freq = freq;
                candidate.key = x;
            }
        }
        //可见route中存储的数据为key:词头下标 value:词尾下标，词的频率
        route.put(i, candidate);
    }

Процесс выбора высокочастотных слов:

  • i=N-1: В маршруте есть только одно начальное значение, N=4, freq=0, что означает, что после последнего раза нет слова Во-первых, частота слова «вверх» в дереве равна -5,45. Вероятность попадания после добавления равна -5,45. Поскольку есть только одно слово, начинающееся с «on», оно сохраняется в маршруте

    (3,) : первые 3 – префикс, вторые 3 – индекс суффикса "上", -5,45 – вероятность его появления;
    (4,): начальная вероятность

  • i=N-2: есть два слова, начинающиеся со слова «рано», а именно «рано» и «утро», частота слова «рано» в словаре составляет сначала -8,33, а следующее слово — «上». суммирование, частота -13,78, затем получаем "утро", частота в словаре -10,81, после слова "утро" нет слова, поэтому значение частоты равно -10,81, сравнивая частоту двух слов, частоту "утро" велико, поэтому сохраняется только "утро"

    В этот момент маршрут сохраняет (3,), (4,) и (2, )

И так далее, слова после маршрута следующие:

код сегментации слова

После взятия высокочастотных слов основная логика выглядит следующим образом.

 while (x < N) {
        //获取当前字符开头的词的词尾
        y = route.get(x).key + 1;
        String lWord = sentence.substring(x, y);
        if (y - x == 1)
            sb.append(lWord); //单个字符成词，先保留
        else {
            if (sb.length() > 0) {
                buf = sb.toString();
                sb = new StringBuilder();
                if (buf.length() == 1) {
                    tokens.add(buf);
                }
                else {
                    if (wordDict.containsWord(buf)) {
                        tokens.add(buf); //多个字符并且字典中存在，作为分词的结果
                    }
                    else {
                        finalSeg.cut(buf, tokens);
                    }
                }
            }
            //保留多个字符组成的词
            tokens.add(lWord);
        }
        x = y; //从当前词的词尾开始找下一个词
    }

процесс извлечения слов

  • x=0, найдите, что его окончание слова равно 1, и получите «сегодня» в это время, поскольку оно содержит несколько слов, оно непосредственно используется как результат сегментации слов.
  • x=2, конец слова равен 3, добраться до «утро», конец сегментации слова

На этом причастие предложения «сегодня утром» заканчивается. Вы можете видеть, что это основано на том факте, что слово уже существует в словаре.
Если в словах есть несколько отдельных слов, таких как «the» в «going out», с одной стороны, оно становится одним словом, а с другой стороны, последующее «of» становится вместе с ним Слово, состоящее из двух символов не существует в словаре 'of', поэтому оно распознается как неизвестное слово, вызывающееfinalSeg.cut

Viterbi алгоритм обрабатывает незаконные слова и повторно идентифицирует их

В качестве метода используется алгоритм Витерби. Сначала предварительно загрузите следующие три набора наборов вероятностей и наборов скрытых состояний модели HMM.

  1. Неизвестные слова определяют 4 скрытых состояния. B означает начало слова M означает середину слова E означает конец слова S означает, что слово становится словом

  2. Инициализировать начальную вероятность каждого скрытого состояния

    start.put('B', -0.26268660809250016);
start.put('E', -3.14e+100);
start.put('M', -3.14e+100);
start.put('S', -1.4652633398537678);

  3. Инициализируйте матрицу перехода состояния

    trans = new HashMap<Character, Map<Character, Double>>();
Map<Character, Double> transB = new HashMap<Character, Double>();
transB.put('E', -0.510825623765990);
transB.put('M', -0.916290731874155);
trans.put('B', transB);
Map<Character, Double> transE = new HashMap<Character, Double>();
transE.put('B', -0.5897149736854513);
transE.put('S', -0.8085250474669937);
trans.put('E', transE);
Map<Character, Double> transM = new HashMap<Character, Double>();
transM.put('E', -0.33344856811948514);
transM.put('M', -1.2603623820268226);
trans.put('M', transM);
Map<Character, Double> transS = new HashMap<Character, Double>();
transS.put('B', -0.7211965654669841);
transS.put('S', -0.6658631448798212);
trans.put('S', transS);

    Например, trans.get('S').get('B') означает, что если текущим символом является 'S', вероятность того, что следующее слово (слово, состоящее из одного слова) начинается с -0,721

  4. Прочитайте матрицу путаницы, подготовленную реализацией, и сохраните ее в emit.

    Красная рамка указывает на то, что при предпосылке скрытого состояния «Е» вероятность того, что наблюдаемое состояние является «хочу», составляет -5,26.
    Красная рамка указывает на то, что при предпосылке скрытого состояния «В» вероятность того, что наблюдаемое состояние является «хочу», составляет -6,73.

Кроме того, он предопределяет только те состояния, которые предшествуют каждому скрытому состоянию.

prevStatus.put('B', new char[] { 'E', 'S' });
prevStatus.put('M', new char[] { 'M', 'B' });
prevStatus.put('S', new char[] { 'S', 'E' });
prevStatus.put('E', new char[] { 'B', 'M' });

Например, перед «М» должна стоять единица между «М» и «В».

Ход алгоритма следующий:

  1. Получить вероятность появления первого символа в предложении во всех скрытых состояниях
      for (char state : states) {
        Double emP = emit.get(state).get(sentence.charAt(0));
        if (null == emP)
            emP = MIN_FLOAT;
        //存储第一个字符 是 'B' 'E' 'M' 'S'的概率，即初始化转移概率
        v.get(0).put(state, start.get(state) + emP);
        path.put(state, new Node(state, null));
    }
  2. Рассчитайте вероятность получения скрытой последовательности на основе последовательности наблюдений и модели HMM и отметьте наилучшую аналитическую позицию, которая связана родительским указателем
for (int i = 1; i < sentence.length(); ++i) {
    Map<Character, Double> vv = new HashMap<Character, Double>();
    v.add(vv);
    Map<Character, Node> newPath = new HashMap<Character, Node>();
    for (char y : states) {
    //y表示隐藏状态
    //emp是获取混淆矩阵的概率，比如 在 'B'发生的情况下，观察到字符 '要' 的概率
        Double emp = emit.get(y).get(sentence.charAt(i));
        if (emp == null)
            emp = MIN_FLOAT; //样本中没有，就设置为最小的概率
        Pair<Character> candidate = null;
        for (char y0 : prevStatus.get(y)) {
            Double tranp = trans.get(y0).get(y);//获取状态转移概率,比如 E -> B
            if (null == tranp)
                tranp = MIN_FLOAT; //转移概率不存在，取最低的
            //v中放的是当前字符的前一个字符的概率，即前一个状态的最优解
            //tranp 是状态转移的概率
            //三者相加即计算已知观察序列和HMM的条件下，求得最可能的隐藏序列的概率
            tranp += (emp + v.get(i - 1).get(y0));
            if (null == candidate)
                candidate = new Pair<Character>(y0, tranp);
            else if (candidate.freq <= tranp) {
            //存储最优可能的隐藏概率
                candidate.freq = tranp;
                candidate.key = y0;
            }
        }
        //存储是'B'还是 'E'各自的概率
        vv.put(y, candidate.freq);
        //记下前后两个词最优的路径，以便还原原始的隐藏状态分隔点
        newPath.put(y, new Node(y, path.get(candidate.key)));
    }
    //存储最终句子的最优路径
    path = newPath;
}
  1. Найдите скрытое состояние символов в конце предложения и используйте лучший путь, чтобы сократить все предложение.
    double probE = v.get(sentence.length() - 1).get('E');
double probS = v.get(sentence.length() - 1).get('S');
Vector<Character> posList = new Vector<Character>(sentence.length());
Node win;
if (probE < probS)
    win = path.get('S');
else
    win = path.get('E');

while (win != null) {
//沿着指针找到句子的每个字符的个子位置
    posList.add(win.value);
    win = win.parent;
}
Collections.reverse(posList);
  2. Проведите это предложение по метке, запишите все слова точки разреза
int begin = 0, next = 0;
for (int i = 0; i < sentence.length(); ++i) {
    char pos = posList.get(i);
    if (pos == 'B')
        begin = i;
    else if (pos == 'E') {
    //到词尾了，记下
        tokens.add(sentence.substring(begin, i + 1));
        next = i + 1;
    }
    else if (pos == 'S') {
    //单个字成词，记下
        tokens.add(sentence.substring(i, i + 1));
        next = i + 1;
    }
}
if (next < sentence.length())
    tokens.add(sentence.substring(next));

Конец исполнения

Исходный код JieBa версии Java

Категории