Phrase Extraction

phrase-extract.js

/**
 * Phrase Extraction
 */

;(function(exports) {

  function extractPhrases(e, f, a) {
    var fStart,
        fEnd,
        result = [];
  
    function alignments() {
      var result = [];
      a.forEach(function(points, i) {
        points.forEach(function(point) {
          result.push([i, point]);
        });
      });
      return result;
    }

    function isAligned(type, i) {
      if (type === 'e') {
        return a[i].length > 0;
      } else if (type === 'f') {
        return a.some(function(points) { return points.indexOf(i) > -1; });
      } else {
        throw new Error('Unknown type ' + type + '.');
      }
    }
    
    function violateConsistency(fStart, fEnd, eStart, eEnd) {
      return alignments().some(function(pair) {
        var e = pair[0],
            f = pair[1];
        if (f < fStart || fEnd < f) {
          return false;
        }
        return (e < eStart || eEnd < e);
      });
    }
    
    function reconstruct(fStart, fEnd, eStart, eEnd) {
      var tmp = [],
          result = [];
      
      while (eStart <= eEnd) {
        tmp.push(e[eStart]);
        eStart++;
      }
      result.push(tmp.join(' '));
      tmp = [];
      while (fStart <= fEnd) {
        tmp.push(f[fStart]);
        fStart++;
      }
      result.push(tmp.join(' '));
      return result;
    }
    
    function extract(fStart, fEnd, eStart, eEnd) {
      var tmpStart,
          tmpEnd,
          result = [];
      
      // もし訳語が指定位置からはみ出していたら失敗とみなす
      if (violateConsistency(fStart, fEnd, eStart, eEnd)) {
        return [];
      }
      tmpStart = fStart;
      do {
        tmpEnd = fEnd;
        do {
          result.push([tmpStart, tmpEnd, eStart, eEnd]);
          // どんどん後ろにのばしていく
          tmpEnd++;
        } while (tmpEnd < f.length && !isAligned('f', tmpEnd))
        // どんどん前にのばしていく
        tmpStart--;
      } while (tmpStart >= 0 && !isAligned('f', tmpStart))
      return result;
    };
    
    // 開始位置と終了位置のループで、想定される訳文のフレーズ候補を洗い出す
    for (var eStart = 0, len = e.length; eStart < len; eStart++) {
      for (var eEnd = eStart; eEnd < len; eEnd++) {
        fStart = f.length - 1;
        fEnd = -1;
        alignments().forEach(function(pair) {
          var e = pair[0],
              f = pair[1];
          if (eStart <= e && e <= eEnd) {
            // 対応する原文の開始位置と終了位置を「長さが最小になるように」計算する
            fStart = Math.min(f, fStart);
            fEnd = Math.max(f, fEnd);
          }
        });
        // もしforEachのループを通っていなかったら（つまり訳語に対応する原語がなかったら）無視する
        if (fEnd === -1) continue;
        // フレーズを抽出する
        result = result.concat(extract(fStart, fEnd, eStart, eEnd));    
      }
    }

    return result.map(function(set) {
      // 単語列に復元する
      return reconstruct.apply(null, set);
    });
  };

  exports.extractPhrases = extractPhrases;

})('object' === typeof module ? module.exports : this);