<commit_before>// @flow strict

/**
 * Given an invalid input string and a list of valid options, returns a filtered
 * list of valid options sorted based on their similarity with the input.
 */
export default function suggestionList(
  input: string,
  options: $ReadOnlyArray<string>,
): Array<string> {
  const optionsByDistance = Object.create(null);
  const lexicalDistance = new LexicalDistance(input);

  const inputThreshold = input.length / 2;
  for (const option of options) {
    const distance = lexicalDistance.measure(option);
    const threshold = Math.max(inputThreshold, option.length / 2, 1);
    if (distance <= threshold) {
      optionsByDistance[option] = distance;
    }
  }
  return Object.keys(optionsByDistance).sort((a, b) => {
    const distanceDiff = optionsByDistance[a] - optionsByDistance[b];
    return distanceDiff !== 0 ? distanceDiff : a.localeCompare(b);
  });
}

/**
 * Computes the lexical distance between strings A and B.
 *
 * The "distance" between two strings is given by counting the minimum number
 * of edits needed to transform string A into string B. An edit can be an
 * insertion, deletion, or substitution of a single character, or a swap of two
 * adjacent characters.
 *
 * Includes a custom alteration from Damerau-Levenshtein to treat case changes
 * as a single edit which helps identify mis-cased values with an edit distance
 * of 1.
 *
 * This distance can be useful for detecting typos in input or sorting
 */
class LexicalDistance {
  _input: string;
  _inputLowerCase: string;
  _cells: Array<Array<number>>;

  constructor(input: string) {
    this._input = input;
    this._inputLowerCase = input.toLowerCase();
    this._cells = [];
  }

  measure(option: string): number {
    if (this._input === option) {
      return 0;
    }

    const optionLowerCase = option.toLowerCase();

    // Any case change counts as a single edit
    if (this._inputLowerCase === optionLowerCase) {
      return 1;
    }

    const d = this._cells;
    const a = optionLowerCase;
    const b = this._inputLowerCase;
    const aLength = a.length;
    const bLength = b.length;

    for (let i = 0; i <= aLength; i++) {
      d[i] = [i];
    }

    for (let j = 1; j <= bLength; j++) {
      d[0][j] = j;
    }

    for (let i = 1; i <= aLength; i++) {
      for (let j = 1; j <= bLength; j++) {
        const cost = a[i - 1] === b[j - 1] ? 0 : 1;

        let currentCell = Math.min(
          d[i - 1][j] + 1, // delete
          d[i][j - 1] + 1, // insert
          d[i - 1][j - 1] + cost, // substitute
        );

        if (i > 1 && j > 1 && a[i - 1] === b[j - 2] && a[i - 2] === b[j - 1]) {
          // transposition
          currentCell = Math.min(currentCell, d[i - 2][j - 2] + 1);
        }

        d[i][j] = currentCell;
      }
    }

    return d[aLength][bLength];
  }
}<commit_msg>suggestionList: use only 3 rows instead of full matrix<commit_after>// @flow strict

/**
 * Given an invalid input string and a list of valid options, returns a filtered
 * list of valid options sorted based on their similarity with the input.
 */
export default function suggestionList(
  input: string,
  options: $ReadOnlyArray<string>,
): Array<string> {
  const optionsByDistance = Object.create(null);
  const lexicalDistance = new LexicalDistance(input);

  const inputThreshold = input.length / 2;
  for (const option of options) {
    const distance = lexicalDistance.measure(option);
    const threshold = Math.max(inputThreshold, option.length / 2, 1);
    if (distance <= threshold) {
      optionsByDistance[option] = distance;
    }
  }
  return Object.keys(optionsByDistance).sort((a, b) => {
    const distanceDiff = optionsByDistance[a] - optionsByDistance[b];
    return distanceDiff !== 0 ? distanceDiff : a.localeCompare(b);
  });
}

/**
 * Computes the lexical distance between strings A and B.
 *
 * The "distance" between two strings is given by counting the minimum number
 * of edits needed to transform string A into string B. An edit can be an
 * insertion, deletion, or substitution of a single character, or a swap of two
 * adjacent characters.
 *
 * Includes a custom alteration from Damerau-Levenshtein to treat case changes
 * as a single edit which helps identify mis-cased values with an edit distance
 * of 1.
 *
 * This distance can be useful for detecting typos in input or sorting
 */
class LexicalDistance {
  _input: string;
  _inputLowerCase: string;
  _rows: [Array<number>, Array<number>, Array<number>];

  constructor(input: string) {
    this._input = input;
    this._inputLowerCase = input.toLowerCase();

    this._rows = [
      new Array(input.length + 1).fill(0),
      new Array(input.length + 1).fill(0),
      new Array(input.length + 1).fill(0),
    ];
  }

  measure(option: string): number {
    if (this._input === option) {
      return 0;
    }

    const optionLowerCase = option.toLowerCase();

    // Any case change counts as a single edit
    if (this._inputLowerCase === optionLowerCase) {
      return 1;
    }

    const a = optionLowerCase;
    const b = this._inputLowerCase;
    const aLength = a.length;
    const bLength = b.length;

    const rows = this._rows;
    for (let j = 0; j <= bLength; j++) {
      rows[0][j] = j;
    }

    for (let i = 1; i <= aLength; i++) {
      const upRow = rows[(i - 1) % 3];
      const currentRow = rows[i % 3];

      currentRow[0] = i;
      for (let j = 1; j <= bLength; j++) {
        const cost = a[i - 1] === b[j - 1] ? 0 : 1;

        let currentCell = Math.min(
          upRow[j] + 1, // delete
          currentRow[j - 1] + 1, // insert
          upRow[j - 1] + cost, // substitute
        );

        if (i > 1 && j > 1 && a[i - 1] === b[j - 2] && a[i - 2] === b[j - 1]) {
          // transposition
          const doubleDiagonalCell = rows[(i - 2) % 3][j - 2];
          currentCell = Math.min(currentCell, doubleDiagonalCell + 1);
        }

        currentRow[j] = currentCell;
      }
    }

    return rows[aLength % 3][bLength];
  }
}
{'fraction_non_alphanumeric': 0.12491683300066533, 'fraction_numerical': 0.011976047904191617, 'mean_word_length': 2.6332326283987917, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 18, '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': '2109428', 'n_tokens_mistral': 1930, 'n_tokens_neox': 1831, 'n_words': 628}