NLP: 중국어 단어 알고리즘 - 정방 향 최대 일치 Forward Maximum Matching

update: 24/3/2015
최근 NLP 중국어 단 어 를 접 했 습 니 다. 일부 특수 환경 요구 로 인해 클 라 이언 트 브 라 우 저 환경 에서 단 어 를 실현 해 야 하기 때문에 lunr. js 를 바탕 으로 trie tree 구 조 를 읽 는 inverted index 를 통 해 중국어 의 최대 정방 향 일치 단 어 를 실현 하 였 습 니 다.
어떤 경우, 우 리 는 서버 에서 중국어 텍스트 단 어 를 진행 할 때 mmseg 알고리즘 을 기반 으로 한 완전한 단어 모듈 을 사용 할 수 있 습 니 다. 예 를 들 어 nodejieba, node - segment, 반고 단어 등 입 니 다. 그러나 클 라 이언 트 환경 에서 우 리 는 이러한 복잡 한 단어 알고리즘 을 사용 하여 단 어 를 나 눌 수 없다. 이 럴 때 이미 생 성 된 색인 에 따라 간단 한 클 라 이언 트 단 어 를 나 눌 수 있다. 즉, FMM (Forward Maximum Matching, 정방 향 최대 일치) 이 고 가끔 은 정방 향 일치 도 사용 할 수 있다.
FMM 을 할 때 는 교 집합 오류 검 사 를 통 해 오류 가 발생 했 는 지, 오류 가 발생 하면 다른 오류 처 리 를 해 야 한다. 다른 의미 처 리 는 bi - gram 또는 다른 의미 의 부분 에 대해 완전한 정방 향 매 칭 을 하여 모든 절 분 될 수 있 는 상황 을 나 눌 수 있 습 니 다. 
FMM (정방 향 최대 일치) 을 할 때 단어의 결 과 는 일치 할 수 있 는 최대 길 이 를 캡 처 하 는 것 이기 때 문 입 니 다.그러나 이 최대 길이 의 일치 가 가장 합 리 적 인 단어 결과 라 고 장담 할 수 없고 다른 단어 결과 가 있 을 수 있다.
예 를 들 어 '탁구 라켓 이 다 팔 렸 다' 는 식 으로 FMM 이 '탁구 라켓' 에 맞 으 면 '탁구', '경매', '망 했다' 라 는 더 합 리 적 인 단어 가 나 올 수 있 기 때문이다.따라서 교 집합 오류 검 사 를 해 야 한다.
잘못된 의 미 를 교차 시 키 는 또 다른 예, 예 를 들 어 '학원 길이 멀다' 는 것 이다. 만약 에 정방 향 최대 일치 만 한다 면 먼저 '학원 길' 을 자 른 다음 에 '길이 멀다' 에 대해 다시 FMM 절 점 을 하 는 것 은 잘못된 것 이다. 
본 고 는 lunr. js 를 바탕 으로 하기 때문에 자 바스 크 립 트 코드 를 사용 하여 실현 합 니 다 (ps: 현재 많은 js 코드 를 썼 습 니 다.... js 코드 를 많이 써 보 니 재 미 있 었 습 니 다.) 저 는 간단 한 10 편의 뉴스 로 색인 을 만 들 었 기 때문에 이곳 의 예 는 이상 적 이지 않 을 수도 있 지만 알고리즘 을 분명하게 묘사 할 수 있 습 니 다.색인 을 구축 하 는 부분 에 대해 서 는 더 이상 설명 하지 않 습 니 다. 우 리 는 색인 이 존재 하고 색인 은 Trie 트 리 로 존재 한다 고 가정 할 뿐 입 니 다. 
ps: JS 파일 을 node. js 로 실행 합 니 다.

var lunr = require("./lunr.js")
var idxdata = require("./idx.json")

var idx = lunr.Index.load(idxdata)
var ii = idx.tokenStore
//console.log(ii.root)

var query1 = "                 "
var query2 = "                  "
var query3 = "                "
var query5 = "   "
var query6 = "          "
var query7 = "    "
var query8 = "   "
var query9 = "     "

query = query6
var result = tokenizer(ii.root, query)
console.log(result)

function tokenizer(root, str) {
  if (root == null || root == undefined) return [];
  if (str == null || str == undefined || str.length == 0) return [];

  var out = [];
  while (str.length > 0) {
    var word = matchLongest(root, str);
    out.push(word);
    str = str.slice(word.length);
  }

  return out;
}

function matchLongest(root, str) {
  if ( root == null || root == undefined ) return
  if ( str == null || str == undefined || str.length == 0 ) return

  var maxMatch = ""
  var currentNode = root
  for( var i = 0; i < str.length; i++ ) {
    if (str[i] in currentNode ) {
      maxMatch += str[i]
      currentNode = currentNode[str[i]]
    } else {
      if ( maxMatch.length == 0 ) maxMatch = str[i]
      break
    }
  }

  return maxMatch
}

function getAmbiguiousLength(root, str, word_length) {
  var i = 1
  while ( i < word_length && i < str.length ) {
    var wid = tokenize(root, str.slice(i))
    wid = wid[0]
    var length = wid.length
    if ( word_length < i + length ) word_length = i + length
    //console.log("i = " + i  + ",length=" + wid.length + ", wid :" + wid + ", word_length : " + word_length)
    i += 1
  }

  return word_length
}

테스트:
1. 
query : "인터넷 금 보 중앙 기상대"
분할 결과: ['인터넷', '금', '보', '중앙 기상대']
2. 
query: "중국 인민 은행 은 우리 나라 가 최근 경기 가 좋 지 않다 고 지적 했다."
분할 결과: ['중국인 민 은행', '지', '출', '나', '국', '최근', '경제', '불황']
여기 서 절 분 효과 가 좋 지 않 은 이 유 는 '우리 나라' 가 단어 가 되 지 않 은 이 유 는 나의 색인 이 너무 작 아서 안에 이런 경로 가 아예 없 기 때문이다.
3. 
query : "중국 은행 이 오늘 최신 대출 정책 을 내 놓 았 다."
분할 결과: ['중국', '은행', '오늘', '출범', '최신', '대출', '돈', '정책']]
주: query 에서 모든 미등 록 어 는 한 글자 로 잘 렸 습 니 다.