viterbi method

void viterbi(String sentence, List<String> tokens)

Implementation

void viterbi(String sentence, List<String> tokens) {
  List<Map<String, double>> v = [];
  Map<String, Node> path = {};

  v.add({});
  for (String state in states) {
    double? emP = emit.get(state)?.get(sentence[0]);
    emP ??= MIN_FLOAT;
    v[0].put(state, start.get(state)! + emP);
    path.put(state, Node(state, null));
  }

  for (int i = 1; i < sentence.length; ++i) {
    Map<String, double> vv = {};
    v.add(vv);
    Map<String, Node> newPath = {};
    for (String y in states) {
      double? emp = emit.get(y)?.get(sentence.charAt(i));
      emp ??= MIN_FLOAT;
      Pair<String>? candidate;
      for (String y0 in prevStatus.get(y)!) {
        double? tranp = trans.get(y0)?.get(y);
        tranp ??= MIN_FLOAT;
        tranp += (emp + v[i - 1].get(y0)!);
        if (null == candidate) {
          candidate = Pair<String>(y0, tranp);
        } else if (candidate.freq <= tranp) {
          candidate.freq = tranp;
          candidate.key = y0;
        }
      }
      vv.put(y, candidate!.freq);
      newPath.put(y, Node(y, path.get(candidate.key)));
    }
    path = newPath;
  }
  double probE = v[sentence.length - 1].get('E')!;
  double probS = v[sentence.length - 1].get('S')!;
  List<String> posList = [];
  Node? win;
  if (probE < probS) {
    win = path.get('S')!;
  } else {
    win = path.get('E')!;
  }

  while (win != null) {
    posList.add(win.value);
    win = win.parent;
  }
  posList = posList.reversed.toList();

  int begin = 0, next = 0;
  for (int i = 0; i < sentence.length; ++i) {
    String pos = posList[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));
  }
}