<commit_before>let _ = require('lodash');
const levenshtein = require('fast-levenshtein');

const Match = require('./data/Match');
const Subtitle = require('./data/Subtitle');
const { convertSecondsToFormat, normalizeString } = require('./utils');

let Combiner = {};

const getRecognizedWordPositions = (wordList) => {
  let map = {};
  wordList.forEach((word, index) => {
    if (!map[word.text]) map[word.text] = [];
    map[word.text].push(index);
  });
  return map;
};

const findCandidatesByRecursion = (items, i, context, cb) => {
  context.push(i);
  cb(_.clone(context));
  items[i].next.forEach(j => {
    findCandidatesByRecursion(items, j, context, cb);
  });
  context.pop();
};

const findPieceInRecognition = (matchContext, piece) => {
  let items = _.sortBy(
    _.flatten(piece.normalizedWords
      .map((word, positionInPiece) => {
        wordPositions = matchContext.positions[word] || [];
        return wordPositions.map(positionInRecognition => ({
          positionInPiece,
          positionInRecognition,
          word,
          next: []
        }));
      })
    ), item => item.positionInRecognition);

  items.forEach((item, i, items) => {
    const remainingWordCountInPiece = (piece.normalizedWords.length - 1 - item.positionInPiece);
    const offsetBound = item.positionInRecognition + remainingWordCountInPiece * 2;
    while (items.length > i+1 && items[i+1].positionInRecognition <= offsetBound) {
      i++;
      const diffPositionInPiece = items[i].positionInPiece - item.positionInPiece;
      const diffPositionInRecognition = items[i].positionInRecognition - item.positionInRecognition;
      if (diffPositionInPiece > 0 && diffPositionInRecognition <= diffPositionInPiece * 2) {
        item.next.push(i);
      }
    }
    if (process.env.NODE_ENV === "DEBUG") console.log(`item=${JSON.stringify(item)} remaining=${remainingWordCountInPiece} until=${offsetBound}`);
  });

  const candidates = [];
  for (let i = 0; i < items.length; i++) {
    findCandidatesByRecursion(items, i, [], (foundCandidate) => {
      const positionsInContext = foundCandidate.map(pos => items[pos].positionInRecognition);
      const foundMatch = new Match(matchContext, positionsInContext)
      candidates.push(foundMatch);
    });
  }
  return (_.takeRight(_.sortBy(candidates, candidate => candidate.positions.length), 20)) || [];
};

const dropUnlikelyCandidates = (matchCandidates) => {
  const maxLength = _.max(matchCandidates.map((candidate) => candidate.positions.length));
  return _.filter(matchCandidates, (candidate) => candidate.positions.length === maxLength);
}

const findLIS = (candidates) => {
  let lisTable = _.times(candidates.length, _.constant(0));
  for (let i = 0; i < candidates.length; i++) {
    const max = candidates
      .map((candidate, index) => {
        const { startTime, endTime, pieceId, data } = candidate;
        return { startTime, endTime, pieceId, index, data };
      })
      .filter((candidate) => {
        const { startTime, endTime, pieceId, index } = candidate;
        return endTime <= candidates[i].startTime && pieceId < candidates[i].pieceId;
      })
      .map((candidate) => lisTable[candidate.index])
      .reduce((a, b) => a > b ? a : b, 0);
    lisTable[i] = max + 1;
  }
  let nextSequenceLength = _.reduce(lisTable, (a, b) => _.max([a, b]));
  let lastSequenceId = 987654321;
  let lis = [];
  for (let i = candidates.length - 1; i >= 0; i--) {
    if (lisTable[i] === nextSequenceLength && candidates[i].pieceId < lastSequenceId) {<commit_msg>Add a FIXME in findLIS<commit_after>let _ = require('lodash');
const levenshtein = require('fast-levenshtein');

const Match = require('./data/Match');
const Subtitle = require('./data/Subtitle');
const { convertSecondsToFormat, normalizeString } = require('./utils');

let Combiner = {};

const getRecognizedWordPositions = (wordList) => {
  let map = {};
  wordList.forEach((word, index) => {
    if (!map[word.text]) map[word.text] = [];
    map[word.text].push(index);
  });
  return map;
};

const findCandidatesByRecursion = (items, i, context, cb) => {
  context.push(i);
  cb(_.clone(context));
  items[i].next.forEach(j => {
    findCandidatesByRecursion(items, j, context, cb);
  });
  context.pop();
};

const findPieceInRecognition = (matchContext, piece) => {
  let items = _.sortBy(
    _.flatten(piece.normalizedWords
      .map((word, positionInPiece) => {
        wordPositions = matchContext.positions[word] || [];
        return wordPositions.map(positionInRecognition => ({
          positionInPiece,
          positionInRecognition,
          word,
          next: []
        }));
      })
    ), item => item.positionInRecognition);

  items.forEach((item, i, items) => {
    const remainingWordCountInPiece = (piece.normalizedWords.length - 1 - item.positionInPiece);
    const offsetBound = item.positionInRecognition + remainingWordCountInPiece * 2;
    while (items.length > i+1 && items[i+1].positionInRecognition <= offsetBound) {
      i++;
      const diffPositionInPiece = items[i].positionInPiece - item.positionInPiece;
      const diffPositionInRecognition = items[i].positionInRecognition - item.positionInRecognition;
      if (diffPositionInPiece > 0 && diffPositionInRecognition <= diffPositionInPiece * 2) {
        item.next.push(i);
      }
    }
    if (process.env.NODE_ENV === "DEBUG") console.log(`item=${JSON.stringify(item)} remaining=${remainingWordCountInPiece} until=${offsetBound}`);
  });

  const candidates = [];
  for (let i = 0; i < items.length; i++) {
    findCandidatesByRecursion(items, i, [], (foundCandidate) => {
      const positionsInContext = foundCandidate.map(pos => items[pos].positionInRecognition);
      const foundMatch = new Match(matchContext, positionsInContext)
      candidates.push(foundMatch);
    });
  }
  return (_.takeRight(_.sortBy(candidates, candidate => candidate.positions.length), 20)) || [];
};

const dropUnlikelyCandidates = (matchCandidates) => {
  const maxLength = _.max(matchCandidates.map((candidate) => candidate.positions.length));
  return _.filter(matchCandidates, (candidate) => candidate.positions.length === maxLength);
}

const findLIS = (candidates) => {
  let lisTable = _.times(candidates.length, _.constant(0));
  for (let i = 0; i < candidates.length; i++) {
    const max = candidates
      .map((candidate, index) => {
        const { startTime, endTime, pieceId, data } = candidate;
        return { startTime, endTime, pieceId, index, data };
      })
      .filter((candidate) => {
        const { startTime, endTime, pieceId, index } = candidate;
        return endTime <= candidates[i].startTime && pieceId < candidates[i].pieceId;
      })
      .map((candidate) => lisTable[candidate.index])
      .reduce((a, b) => a > b ? a : b, 0);
    lisTable[i] = max + 1;
  }
  // FIXME: It is possible there are not unique LIS result
  let nextSequenceLength = _.reduce(lisTable, (a, b) => _.max([a, b]));
  let lastSequenceId = 987654321;
  let lis = [];
  for (let i = candidates.length - 1; i >= 0; i--) {
    if (lisTable[i] === nextSequenceLength && candidates[i].pieceId < lastSequenceId) {
{'fraction_non_alphanumeric': 0.15519171564511614, 'fraction_numerical': 0.006717044500419815, 'mean_word_length': 3.6348897535667963, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 53, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1725431', 'n_tokens_mistral': 2318, 'n_tokens_neox': 2213, 'n_words': 460}