23.12.2024 08:06
aio350 0 706 Источник


Привет, друзья!


В этой серии статей мы разбираем структуры данных и алгоритмы, представленные в этом замечательном репозитории. Это седьмая часть серии.


Сегодня мы поговорим об алгоритмах для работы со строками и поиска.


Код, представленный в этой и других статьях серии, можно найти в этом репозитории.


Интересно? Тогда прошу под кат.



❯ Строки


Прежде чем переходить к изучению конкретных алгоритмов, рекомендую хотя бы вкратце ознакомиться с тем, что такое динамическое программирование. Вот парочка ссылок:



❯ Расстояние Хэмминга


Описание



Расстояние Хэмминга (кодовое расстояние) (Hamming distance) — это число позиций, в которых соответствующие символы двух строк одинаковой длины различны. Другими словами, этот алгоритм измеряет минимальное количество замен символов, которые необходимо произвести для преобразования одной строки в другую. В более общем случае расстояние Хэмминга применяется для строк одинаковой длины и служит метрикой различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности.


Примеры


Расстояние Хэмминга между:


  • "karolin" и "kathrin" составляет 3
  • "karolin" и "kerstin" составляет 3
  • 1011101 и 1001001 составляет 2
  • 2173896 и 2233796 составляет 3

Реализация


// algorithms/strings/hamming-distance.js
export default function hammingDistance(x, y) {
  if (x.length !== y.length) {
    throw new Error('Строки должны иметь одинаковую длину')
  }

  let distance = 0

  for (let i = 0; i < x.length; i++) {
    if (x[i] !== y[i]) {
      distance++
    }
  }

  return distance
}

Тестирование


// algorithms/strings/__tests__/hamming-distance.test.js
import hammingDistance from '../hamming-distance'

describe('hammingDistance', () => {
  it('должен выбросить исключение при сравнении строк разной длины', () => {
    const compareStringsOfDifferentLength = () => {
      hammingDistance('a', 'aa')
    }

    expect(compareStringsOfDifferentLength).toThrowError()
  })

  it('должен вычислить расстояния Хэмминга между двумя строками', () => {
    expect(hammingDistance('a', 'a')).toBe(0)
    expect(hammingDistance('a', 'b')).toBe(1)
    expect(hammingDistance('abc', 'add')).toBe(2)
    expect(hammingDistance('karolin', 'kathrin')).toBe(3)
    expect(hammingDistance('karolin', 'kerstin')).toBe(3)
    expect(hammingDistance('1011101', '1001001')).toBe(2)
    expect(hammingDistance('2173896', '2233796')).toBe(3)
  })
})

Запускаем тесты:


npm run test ./algorithms/strings/__tests__/hamming-distance

Результат:





❯ Расстояние Левенштейна


Описание



Расстояние Левенштейна (редакционное расстояние, дистанция редактирования) (Levenshtein distance) — это метрика, измеряющая по модулю разность между двумя последовательностями символов. Она определяется как минимальное количество односимвольных операций (вставки, удаления или замены), необходимых для превращения одной последовательности символов в другую.


Определение


Математически, расстояние Левенштейна между двумя строками a и b (длиной |a| и |b|, соответственно) определяется с помощью





где





Здесь





это индикаторная функция (indicator function), равная 0, когда





и 1, в противном случае, а





это расстояние между первыми i символами a и первыми j символами b.


Обратите внимание, что первый элемент min соответствует удалению, второй — вставке, третий — совпадению или несовпадению в зависимости от одинаковости символов.


Пример


Расстояние Левенштейна между kitten и sitting равняется 3, поскольку для преобразования первой строки во вторую необходимо выполнить следующие операции:


  • kitten -> sitten (замена k на s)
  • sitten -> sittin (замена e на i)
  • sittin -> sitting (вставка g в конец)

Применение


Рассматриваемый алгоритм применяется в большом количестве приложений, например, в средствах проверки орфографии, системах исправлений для оптического распознавания символов, неточного (fuzzy) поиска строк и программном обеспечении для облегчения перевода на естественный язык.


Динамическое программирование


Рассмотрим простой пример нахождения минимального редакционного расстояния между строками ME и MY. Интуитивно мы понимаем, что оно равняется 1 операции, которой является замена E на Y. Однако давайте формализуем это в алгоритм, чтобы иметь возможность решать более сложные задачи, например, задачу преобразования Saturday в Sunday.


Для применения указанной выше математической формулы к преобразованию ME -> MY нам для начала нужно вычислить минимальные расстояния ME -> M, M -> MY и M -> M. Затем надо взять минимальное расстояние и добавить одну операцию для замены E на Y. Поэтому минимальное редакционное расстояние трансформации ME -> MY вычисляется на основе трех предыдущих возможных преобразований.


Нарисуем матрицу:





  • Ячейка (0:1) содержит красное число 1. Это означает, что для преобразования M в пустую строку требуется 1 операция. Этой операцией является удаление. Вот почему число красное
  • ячейка (0:2) содержит красное число 2. Это означает, что для преобразования ME в пустую строку требуется 2 операции. Этими операциями являются удаление E и M
  • ячейка (1:0) содержит зеленое число 1. Это означает, что для преобразования пустой строки в M требуется 1 операция. Этой операцией является вставка M. Вот почему число зеленое
  • ячейка (2:0) содержит зеленое число 2. Это означает, что для преобразования пустой строки в MY требуется 2 операции. Этими операциями являются вставка Y и M
  • ячейка (1:1) содержит число 0. Это означает, что для преобразования M в M ничего делать не нужно
  • ячейка (1:2) содержит красное число 1. Это означает, что для преобразования ME в M требуется 1 операция. Этой операцией является удаление E
  • и т.д.

Для небольших матриц (в нашем случае 3x3) все выглядит просто, но тоже самое применяется для вычисления таких чисел для больших матриц (например, 9x7 для преобразования Saturday -> Sunday).


Согласно формуле нам нужны 3 соседние ячейки (i-1:j), (i-1:j-1) и (i:j-1) для вычисления числа для текущей ячейки (i:j). Все, что нужно сделать — найти минимальную соседнюю ячейку и прибавить к ней 1 в случае, если строка i и колонка j содержат разные символы.


Рекурсивную природу задачи можно проиллюстрировать следующим образом:





Нарисуем граф решений для этой задачи:





Вы можете видеть количество перекрывающихся задач, которые помечены желтым. Не существует способа уменьшить количество операций и сделать его меньше минимальной из этих трех ячеек.


Также можно видеть, что каждое число ячейки вычисляется на основе предыдущих. Поэтому здесь применяется техника табулирования (заполнение кэша снизу вверх).


Дальнейшее применение этого принципа позволяет решать более сложные задачи, например, преобразование Saturday -> Sunday:





Реализация


// algorithms/strings/levenshtein-distance.js
export default function levenshteinDistance(a, b) {
  // Создаем пустую матрицу редактирования
  const matrix = new Array(b.length + 1)
    .fill(null)
    .map(() => new Array(a.length + 1).fill(null))

  // Заполняем первую строку матрицы.
  // Если это первая строка, тогда мы преобразуем пустую строку в `a`.
  // В этом случае количество модификаций равняется размеру подстроки
  for (let i = 0; i <= a.length; i++) {
    matrix[0][i] = i
  }

  // Заполняем первую колонку матрицы.
  // Если это первая колонка, тогда мы преобразуем пустую строку в `b`.
  // В этом случае количество модификаций равняется размеру подстроки
  for (let j = 0; j <= b.length; j++) {
    matrix[j][0] = j
  }

  // Заполняем матрицу редактирования
  for (let j = 1; j <= b.length; j++) {
    for (let i = 1; i <= a.length; i++) {
      const indicator = b[j - 1] === a[i - 1] ? 0 : 1
      matrix[j][i] = Math.min(
        matrix[j][i - 1] + 1, // удаление
        matrix[j - 1][i] + 1, // вставка
        matrix[j - 1][i - 1] + indicator, // замена
      )
    }
  }

  return matrix[b.length][a.length]
}

Тестирование


// algorithms/strings/__tests__/levenshtein-distance.test.js
import levenshteinDistance from '../levenshtein-distance'

describe('levenshteinDistance', () => {
  it('должен вычислить расстояния Левенштейна между двумя строками', () => {
    expect(levenshteinDistance('', '')).toBe(0)
    expect(levenshteinDistance('a', '')).toBe(1)
    expect(levenshteinDistance('', 'a')).toBe(1)
    expect(levenshteinDistance('abc', '')).toBe(3)
    expect(levenshteinDistance('', 'abc')).toBe(3)

    // Нужно добавить `I` в начало
    expect(levenshteinDistance('islander', 'slander')).toBe(1)

    // Нужно заменить `M` на `K`, `T` на `M` и добавить `A` в конец
    expect(levenshteinDistance('mart', 'karma')).toBe(3)

    // Нужно заменить `K` на `S`, `E` на `I` и добавить `G` в конец
    expect(levenshteinDistance('kitten', 'sitting')).toBe(3)

    // Нужно добавить 4 буквы `FOOT` в начало
    expect(levenshteinDistance('ball', 'football')).toBe(4)

    // Нужно удалить 4 буквы `FOOT` в начале
    expect(levenshteinDistance('football', 'foot')).toBe(4)

    // Нужно заменить первые 5 букв `INTEN` на `EXECU`
    expect(levenshteinDistance('intention', 'execution')).toBe(5)
  })
})

Запускаем тесты:


npm run test ./algorithms/strings/__tests__/levenshtein-distance

Результат:





❯ Алгоритм Кнута-Морриса-Пратта


Описание



Алгоритм Кнута-Морриса-Пратта (КМП-алгоритм) (Knuth–Morris–Pratt algorithm) — эффективный алгоритм, осуществляющий поиск подстроки в строке, используя то, что при возникновении несоответствия само слово содержит достаточно информации, чтобы определить, где может начаться следующее совпадение, минуя лишние проверки. Время работы алгоритма линейно зависит от объема входных данных, то есть разработать асимптотически более эффективный алгоритм невозможно.


Задача


Даны образец (строка) S и строка T. Требуется определить индекс, начиная с которого образец S содержится в строке T. Если S не содержится в T, нужно вернуть индекс, который не может быть интерпретирован как позиция в строке (например, отрицательное число).


Сложность


  • Временная: O(|W| + |T|) (что гораздо быстрее тривиального O(|W| * |T|))
  • пространственная: O(|W|)

Реализация


Начнем с определения функции для создания временной таблицы паттерна:


// algorithms/strings/knuth-morris-pratt.js
function buildPatternTable(word) {
  const patternTable = [0]
  let prefixIndex = 0
  let suffixIndex = 1

  while (suffixIndex < word.length) {
    if (word[suffixIndex] === word[prefixIndex]) {
      patternTable[suffixIndex] = prefixIndex + 1
      prefixIndex += 1
      suffixIndex += 1
    } else if (prefixIndex === 0) {
      patternTable[suffixIndex] = 0
      suffixIndex += 1
    } else {
      prefixIndex = patternTable[prefixIndex - 1]
    }
  }

  return patternTable
}

Используем эту таблицу для решения задачи:


export default function knuthMorrisPratt(text, word) {
  if (word.length === 0) return 0

  let textIndex = 0
  let wordIndex = 0

  const patternTable = buildPatternTable(word)

  while (textIndex < text.length) {
    if (text[textIndex] === word[wordIndex]) {
      // Найдено совпадение
      if (wordIndex === word.length - 1) {
        return textIndex - word.length + 1
      }

      textIndex += 1
      wordIndex += 1
    } else if (wordIndex > 0) {
      wordIndex = patternTable[wordIndex - 1]
    } else {
      textIndex += 1
    }
  }

  return -1
}

Тестирование


// algorithms/strings/__tests__/knuth-morris-pratt.test.js
import knuthMorrisPratt from '../knuth-morris-pratt'

describe('knuthMorrisPratt', () => {
  it('должен найти начальные индексы слов в текстах', () => {
    expect(knuthMorrisPratt('', '')).toBe(0)
    expect(knuthMorrisPratt('a', '')).toBe(0)
    expect(knuthMorrisPratt('a', 'a')).toBe(0)
    expect(knuthMorrisPratt('abcbcglx', 'abca')).toBe(-1)
    expect(knuthMorrisPratt('abcbcglx', 'bcgl')).toBe(3)
    expect(knuthMorrisPratt('abcxabcdabxabcdabcdabcy', 'abcdabcy')).toBe(15)
    expect(knuthMorrisPratt('abcxabcdabxabcdabcdabcy', 'abcdabca')).toBe(-1)
    expect(
      knuthMorrisPratt('abcxabcdabxaabcdabcabcdabcdabcy', 'abcdabca'),
    ).toBe(12)
    expect(
      knuthMorrisPratt('abcxabcdabxaabaabaaaabcdabcdabcy', 'aabaabaaa'),
    ).toBe(11)
  })
})

Запускаем тесты:


npm run test ./algorithms/strings/__tests__/knuth-morris-pratt

Результат:





❯ Алгоритм Рабина-Карпа


Описание



Алгоритм Рабина-Карпа (Rabin-Karp Algorithm) — это алгоритм поиска строки, который ищет шаблон, то есть подстроку, в тексте, используя хэширование.



Алгоритм редко используется для поиска одиночного шаблона, но имеет значительную теоретическую важность и очень эффективен в поиске совпадений множественных шаблонов одинаковой длины. Хэш-функция — это функция, которая преобразует каждую строку в числовое значение, которое называется хэшем. Например, мы можем получить hash('hello') = 5. Алгоритм исходит из предположения, что одинаковые строки имеют одинаковый хэш. Поэтому задача поиска подстроки сводится к вычислению хэша искомого паттерна и поиск подстрок входной строки, которые имеют такой же хэш.


Однако у рассматриваемого алгоритма есть две проблемы. Во-первых, строк много, а хэшей мало, поэтому разные строки могут иметь одинаковый хэш. Другими словами, при совпадении хэшей паттерн и подстрока могут не совпадать. Поэтому совпадение паттерна с подстрокой должно проверяться путем их сравнения. Такое сравнение может занять много времени для больших подстрок. К счастью, хорошая функция хэширования, применяемая к строкам разумной длины, как правило, имеет мало коллизий, поэтому ожидаемое время поиска является приемлемым.


Хэш-функция


Источником производительности алгоритма Рабина-Карпа является эффективное вычисление хэшей последовательных подстрок текста. Популярной и эффективной скользящей (rolling) хэш-функцией является отпечаток Рабина (Rabin fingerprint).


Мы будем использовать полиномиальную функцию хэширования, которая почти также хороша, как отпечаток Рабина. Она преобразует каждую подстроку в число в некотором основании, причем основанием обычно является большое простое число.


Сложность


Для текста длиной n и паттернов p общей длиной m среднее и лучшее время составляет O(n + m) в пространстве O(p), в худшем случае время составляет O(n * m).


Применение


Одно из простейших практических применений алгоритма Рабина-Карпа состоит в определении плагиата. Алгоритм может быстро находить в документе экземпляры предложений из исходного материала, игнорируя такие детали, как регистр и пунктуация. В этом случае из-за обилия искомых строк алгоритмы однострочного поиска неэффективны.


Реализация


Начнем с реализации полиномиальной функции хэширования:


// algorithms/cryptography/polynomial-hash.js
const DEFAULT_BASE = 37
const DEFAULT_MODULUS = 101

export default class PolynomialHash {
  /**
   * @param {number} [base] - Базовое число, которое используется для создания полинома.
   * @param {number} [modulus] - Модульное число, которое защищает хэш от переполнения.
   */
  constructor({ base = DEFAULT_BASE, modulus = DEFAULT_MODULUS } = {}) {
    this.base = base
    this.modulus = modulus
  }

  /**
   * Функция, создающее хэшированное значение слова.
   *
   * Временная сложность: O(word.length).
   *
   * @param {string} word - Строка для хэширования.
   * @return {number}
   */
  hash(word) {
    const charCodes = Array.from(word).map((char) => this.charToNumber(char))

    let hash = 0
    for (let charIndex = 0; charIndex < charCodes.length; charIndex += 1) {
      hash *= this.base
      hash += charCodes[charIndex]
      hash %= this.modulus
    }

    return hash
  }

  /**
   * Функция, генерирующая хэш слова на основе
   * хэша предыдущего слова (сдвинутого на один символ влево).
   *
   * Повторно вычисляет хэш слова, чтобы не анализировать все слово заново.
   *
   * Временная сложность: O(1).
   *
   * @param {number} prevHash
   * @param {string} prevWord
   * @param {string} newWord
   * @return {number}
   */
  roll(prevHash, prevWord, newWord) {
    let hash = prevHash

    const prevValue = this.charToNumber(prevWord[0])
    const newValue = this.charToNumber(newWord[newWord.length - 1])

    let prevValueMultiplier = 1
    for (let i = 1; i < prevWord.length; i += 1) {
      prevValueMultiplier *= this.base
      prevValueMultiplier %= this.modulus
    }

    hash += this.modulus
    hash -= (prevValue * prevValueMultiplier) % this.modulus

    hash *= this.base
    hash += newValue
    hash %= this.modulus

    return hash
  }

  /**
   * Преобразует символ в число.
   *
   * @param {string} char
   * @return {number}
   */
  charToNumber(char) {
    let charCode = char.codePointAt(0)

    // Проверяем, является ли символ суррогатной парой.
    const surrogate = char.codePointAt(1)
    if (surrogate !== undefined) {
      const surrogateShift = 2 ** 16
      charCode += surrogate * surrogateShift
    }

    return charCode
  }
}

Используем эту функцию для реализации алгоритма Рабина-Карпа:


// algorithms/strings/rabin-karp.js
import PolynomialHash from '../cryptography/polynomial-hash'

export default function rabinKarp(text, word) {
  const hasher = new PolynomialHash()

  // Вычисляем хэш слова, который будет использоваться для сравнения с хэшами подстрок
  const wordHash = hasher.hash(word)

  let prevFrame = null
  let currentFrameHash = null

  // Перебираем все подстроки текста, которые могут совпасть
  for (let i = 0; i < text.length - word.length + 1; i++) {
    const currentFrame = text.slice(i, i + word.length)

    // Вычисляем хэш текущей подстроки
    if (!currentFrameHash) {
      currentFrameHash = hasher.hash(currentFrame)
    } else {
      currentFrameHash = hasher.roll(currentFrameHash, prevFrame, currentFrame)
    }

    prevFrame = currentFrame

    // Сравниваем хэш текущей подстроки с искомым паттерном.
    // При совпадении хэшей, проверяем равенство подстрок на случай коллизии хэшей
    if (
      wordHash === currentFrameHash &&
      text.slice(i, i + word.length) === word
    ) {
      return i
    }
  }

  return -1
}

Тестирование


// algorithms/strings/__tests__/rabin-karp.test.js
import rabinKarp from '../rabin-karp'

describe('rabinKarp', () => {
  it('должен найти подстроки в строке', () => {
    expect(rabinKarp('', '')).toBe(0)
    expect(rabinKarp('a', '')).toBe(0)
    expect(rabinKarp('a', 'a')).toBe(0)
    expect(rabinKarp('ab', 'b')).toBe(1)
    expect(rabinKarp('abcbcglx', 'abca')).toBe(-1)
    expect(rabinKarp('abcbcglx', 'bcgl')).toBe(3)
    expect(rabinKarp('abcxabcdabxabcdabcdabcy', 'abcdabcy')).toBe(15)
    expect(rabinKarp('abcxabcdabxabcdabcdabcy', 'abcdabca')).toBe(-1)
    expect(rabinKarp('abcxabcdabxaabcdabcabcdabcdabcy', 'abcdabca')).toBe(12)
    expect(rabinKarp('abcxabcdabxaabaabaaaabcdabcdabcy', 'aabaabaaa')).toBe(11)
    expect(rabinKarp("^ !/'#'pp", " !/'#'pp")).toBe(1)
  })

  it('должен работать с большими текстами', () => {
    const text =
      'Lorem Ipsum is simply dummy text of the printing and ' +
      "typesetting industry. Lorem Ipsum has been the industry's standard " +
      'dummy text ever since the 1500s, when an unknown printer took a ' +
      'galley of type and scrambled it to make a type specimen book. It ' +
      'has survived not only five centuries, but also the leap into ' +
      'electronic typesetting, remaining essentially unchanged. It was ' +
      'popularised in the 1960s with the release of Letraset sheets ' +
      'containing Lorem Ipsum passages, and more recently with desktop' +
      'publishing software like Aldus PageMaker including versions of Lorem ' +
      'Ipsum.'

    expect(rabinKarp(text, 'Lorem')).toBe(0)
    expect(rabinKarp(text, 'versions')).toBe(549)
    expect(rabinKarp(text, 'versions of Lorem Ipsum.')).toBe(549)
    expect(rabinKarp(text, 'versions of Lorem Ipsum:')).toBe(-1)
    expect(
      rabinKarp(text, 'Lorem Ipsum passages, and more recently with'),
    ).toBe(446)
  })

  it('должен работать с символами UTF', () => {
    expect(rabinKarp('a\u{ffff}', '\u{ffff}')).toBe(1)
    expect(rabinKarp('\u0000耀\u0000', '耀\u0000')).toBe(1)
  })
})

Запускаем тесты:


npm run test ./algorithms/strings/__tests__/rabin-karp

Результат:





❯ Наибольшая общая подстрока


Описание



Наибольшая общая подстрока (longest common substring) — это подстрока двух или более строк, имеющая максимальную длину. Не путайте с наибольшей общей подпоследовательностью.


Пример


НОП строк ABABC, BABCA и ABCBA — строка ABC длиной 3. Другими общими подстроками являются A, AB, B, BA, BC и C.


ABABC
  |||
 BABCA
  |||
  ABCBA

Реализация


// algorithms/strings/longest-common-substring.js
export default function longestCommonSubstring(str1, str2) {
  const s1 = [...str1]
  const s2 = [...str2]

  const matrix = new Array(s2.length + 1)
    .fill(null)
    .map(() => new Array(s1.length + 1).fill(null))

  // Заполняем первую строку и первую колонку `0`
  for (let columnIndex = 0; columnIndex <= s1.length; columnIndex++) {
    matrix[0][columnIndex] = 0
  }
  for (let rowIndex = 0; rowIndex <= s2.length; rowIndex++) {
    matrix[rowIndex][0] = 0
  }

  let longestSubstringLength = 0
  let longestSubstringColumn = 0
  let longestSubstringRow = 0

  for (let rowIndex = 1; rowIndex <= s2.length; rowIndex++) {
    for (let columnIndex = 1; columnIndex <= s1.length; columnIndex++) {
      if (s1[columnIndex - 1] === s2[rowIndex - 1]) {
        matrix[rowIndex][columnIndex] =
          matrix[rowIndex - 1][columnIndex - 1] + 1
      } else {
        matrix[rowIndex][columnIndex] = 0
      }

      // Ищем наибольшую длину
      if (matrix[rowIndex][columnIndex] > longestSubstringLength) {
        longestSubstringLength = matrix[rowIndex][columnIndex]
        longestSubstringColumn = columnIndex
        longestSubstringRow = rowIndex
      }
    }
  }

  // Самая длинная подстрока не найдена
  if (longestSubstringLength === 0) {
    return ''
  }

  // Извлекаем самую длинную подстроку из матрицы
  // путем конкатенации символов
  let longestSubstring = ''

  while (matrix[longestSubstringRow][longestSubstringColumn] > 0) {
    longestSubstring = s1[longestSubstringColumn - 1] + longestSubstring
    longestSubstringColumn--
    longestSubstringRow--
  }

  return longestSubstring
}

Тестирование


// algorithms/strings/__tests__/longest-common-substring.test.js
import longestCommonSubstring from '../longest-common-substring'

describe('longestCommonSubstring', () => {
  it('должен найти наибольшие общие подстроки двух строк', () => {
    expect(longestCommonSubstring('', '')).toBe('')
    expect(longestCommonSubstring('ABC', '')).toBe('')
    expect(longestCommonSubstring('', 'ABC')).toBe('')
    expect(longestCommonSubstring('ABABC', 'BABCA')).toBe('BABC')
    expect(longestCommonSubstring('BABCA', 'ABCBA')).toBe('ABC')
    expect(longestCommonSubstring('sea', 'eat')).toBe('ea')
    expect(longestCommonSubstring('algorithms', 'rithm')).toBe('rithm')
    expect(
      longestCommonSubstring(
        'Algorithms and data structures implemented in JavaScript',
        'Here you may find Algorithms and data structures that are implemented in JavaScript',
      ),
    ).toBe('Algorithms and data structures ')
  })

  it('должен правильно обрабатываться юникод', () => {
    expect(longestCommonSubstring('??**ABC', '??--ABC')).toBe('ABC')
    expect(longestCommonSubstring('??**A', '??--A')).toBe('??')
    expect(longestCommonSubstring('A买B时', '买B时GD')).toBe('买B时')
    expect(
      longestCommonSubstring('After test买时 case', 'another_test买时'),
    ).toBe('test买时')
  })
})

Запускаем тесты:


npm run test ./algorithms/strings/__tests__/longest-common-substring

Результат:





❯ Поиск


❯ Линейный поиск


Описание



Линейный (последовательный) поиск (linear search) — это метод поиска целевого значения в списке (массиве). Он последовательно проверяет каждый элемент списка на предмет совпадения с целевым значением до тех пор, пока либо не будет найдено совпадение, либо не закончатся элементы. Линейный поиск в худшем случае выполняется за линейное время и выполняет n сравнений, где n — это длина массива. Таким образом, временная сложность данного алгоритма составляет O(n).





Реализация


Для сравнения элементов списка с целевым значением будет использоваться кастомная функция, которую мы рассматривали в самой первой статье серии. Напомню, как она выглядит:


// utils/Comparator.js
export default class Comparator {
  constructor(fn) {
    this.compare = fn || Comparator.defaultCompare
  }

  // Дефолтная функция сравнения узлов
  static defaultCompare(a, b) {
    if (a === b) {
      return 0
    }
    return a < b ? -1 : 1
  }

  // Проверка на равенство
  equal(a, b) {
    return this.compare(a, b) === 0
  }

  // Меньше чем
  lessThan(a, b) {
    return this.compare(a, b) < 0
  }

  // Больше чем
  greaterThan(a, b) {
    return this.compare(a, b) > 0
  }

  // Меньше или равно
  lessThanOrEqual(a, b) {
    return this.lessThan(a, b) || this.equal(a, b)
  }

  // Больше или равно
  greaterThanOrEqual(a, b) {
    return this.greaterThan(a, b) || this.equal(a, b)
  }

  // Инверсия сравнения
  reverse() {
    const original = this.compare
    this.compare = (a, b) => original(b, a)
  }
}

Эта функция позволяет сравнивать не только примитивные значение, но и объекты.


Используем ее для реализации алгоритма линейного поиска:


// algorithms/searches/linear-search.js
import Comparator from '../../utils/comparator'

export default function linearSearch(arr, target, fn) {
  const comparator = new Comparator(fn)
  const result = []

  arr.forEach((item, index) => {
    if (comparator.equal(item, target)) {
      result.push(index)
    }
  })

  return result
}

Тестирование


// algorithms/searches/__tests__/linear-search.test.js
import linearSearch from '../linear-search'

describe('linearSearch', () => {
  it('должен найти числа в массиве', () => {
    const array = [1, 2, 4, 6, 2]

    expect(linearSearch(array, 10)).toEqual([])
    expect(linearSearch(array, 1)).toEqual([0])
    expect(linearSearch(array, 2)).toEqual([1, 4])
  })

  it('должен найти символы в массиве', () => {
    const array = ['a', 'b', 'a']

    expect(linearSearch(array, 'c')).toEqual([])
    expect(linearSearch(array, 'b')).toEqual([1])
    expect(linearSearch(array, 'a')).toEqual([0, 2])
  })

  it('должен найти объекты в массиве', () => {
    const comparatorCallback = (a, b) => {
      if (a.key === b.key) {
        return 0
      }

      return a.key <= b.key ? -1 : 1
    }

    const array = [{ key: 5 }, { key: 6 }, { key: 7 }, { key: 6 }]

    expect(linearSearch(array, { key: 10 }, comparatorCallback)).toEqual([])
    expect(linearSearch(array, { key: 5 }, comparatorCallback)).toEqual([0])
    expect(linearSearch(array, { key: 6 }, comparatorCallback)).toEqual([1, 3])
  })
})

Запускаем тесты:


npm run test ./algorithms/searches/__tests__/linear-search

Результат:





❯ Поиск с переходом


Описание



Поиск с переходом (блочный поиск) (jump/block search) — это поисковый алгоритм для отсортированных массивов. Основная идея заключается в проверке меньшего количества элементов (чем при линейном поиске) за счет переходов определенными шагами или пропуска некоторых элементов, вместо проверки всех.


Например, у нас есть массив arr размером n и блок (для перехода) размером m. Мы проверяем индексы arr[0], arr[m], arr[2 * m], ..., arr[k * m], пока не найдем интервал arr[k * m] < x < arr[(k+1) * m], где x — искомое значение. Затем для нахождения x выполняется линейный поиск, начиная с индекса k * m.


Каков оптимальный размер блока? В худшем случае нам придется выполнить n/m переходов, и если последнее проверенное значение больше, чем искомое, мы выполняем m - 1 сравнений линейного поиска. Поэтому общее количество сравнений в худшем случае составляет ((n/m) + m - 1). Значение функции ((n/m) + m - 1) будет минимальным при m = √n. Поэтому лучшим размером блока является √n. Это определяет временную сложность алгоритма — O(√n).


Реализация


// algorithms/searches/jump-search.js
import Comparator from '../../utils/comparator'

export default function jumpSearch(sortedArr, target, fn) {
  const comparator = new Comparator(fn)
  const length = sortedArr.length
  if (!length) return -1

  // Вычисляем оптимальный шаг.
  // Общее количество сравнений в худшем случае будет ((length/step) + step - 1).
  // Значение функции ((length/step) + step - 1) будет минимальным при step = √length
  let step = Math.floor(Math.sqrt(length))

  let start = 0
  let end = step

  // Ищем блок, к которому принадлежит искомый элемент
  while (comparator.greaterThan(target, sortedArr[Math.min(end, length) - 1])) {
    // Переходим к следующему блоку
    start = end
    end += step

    if (start > length) return -1
  }

  // Выполняем линейный поиск в блоке, к которому принадлежит
  // `target`, начиная со `start`
  let currentIndex = start
  while (currentIndex < Math.min(end, length)) {
    if (comparator.equal(target, sortedArr[currentIndex])) {
      return currentIndex
    }
    currentIndex++
  }

  return -1
}

Тестирование


// algorithms/searches/__tests__/jump-search.test.js
import jumpSearch from '../jump-search'

describe('jumpSearch', () => {
  it('должен найти числа в отсортированных массивах', () => {
    expect(jumpSearch([], 1)).toBe(-1)
    expect(jumpSearch([1], 2)).toBe(-1)
    expect(jumpSearch([1], 1)).toBe(0)
    expect(jumpSearch([1, 2], 1)).toBe(0)
    expect(jumpSearch([1, 2], 1)).toBe(0)
    expect(jumpSearch([1, 1, 1], 1)).toBe(0)
    expect(jumpSearch([1, 2, 5, 10, 20, 21, 24, 30, 48], 2)).toBe(1)
    expect(jumpSearch([1, 2, 5, 10, 20, 21, 24, 30, 48], 0)).toBe(-1)
    expect(jumpSearch([1, 2, 5, 10, 20, 21, 24, 30, 48], 0)).toBe(-1)
    expect(jumpSearch([1, 2, 5, 10, 20, 21, 24, 30, 48], 7)).toBe(-1)
    expect(jumpSearch([1, 2, 5, 10, 20, 21, 24, 30, 48], 5)).toBe(2)
    expect(jumpSearch([1, 2, 5, 10, 20, 21, 24, 30, 48], 20)).toBe(4)
    expect(jumpSearch([1, 2, 5, 10, 20, 21, 24, 30, 48], 30)).toBe(7)
    expect(jumpSearch([1, 2, 5, 10, 20, 21, 24, 30, 48], 48)).toBe(8)
  })

  it('должен найти объекты в отсортированном массиве', () => {
    const sortedArrayOfObjects = [
      { key: 1, value: 'value1' },
      { key: 2, value: 'value2' },
      { key: 3, value: 'value3' },
    ]

    const comparator = (a, b) => {
      if (a.key === b.key) return 0
      return a.key < b.key ? -1 : 1
    }

    expect(jumpSearch([], { key: 1 }, comparator)).toBe(-1)
    expect(jumpSearch(sortedArrayOfObjects, { key: 4 }, comparator)).toBe(-1)
    expect(jumpSearch(sortedArrayOfObjects, { key: 1 }, comparator)).toBe(0)
    expect(jumpSearch(sortedArrayOfObjects, { key: 2 }, comparator)).toBe(1)
    expect(jumpSearch(sortedArrayOfObjects, { key: 3 }, comparator)).toBe(2)
  })
})

Запускаем тесты:


npm run test ./algorithms/searches/__tests__/jump-search

Результат:





❯ Двоичный поиск


Описание



Двоичный (бинарный) поиск (метод деления пополам или дихотомия) (binary/half-interval/logarithmic search, binary chop) -это классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Суть такая: мы сравниваем целевое значение с центральным элементом массива. Если они неравны, половина, в которой точно нет целевого значения, отбрасывается, и поиск продолжается в другой половине по такому же принципу. Если поиск завершился пустым массивом, значит, целевое значение в массиве отсутствует.





Временная сложность алгоритма составляет O(log(n)), поскольку мы уменьшаем площадь поиска вдвое на каждой итерации.


Реализация


// algorithms/searches/binary-search.js
import Comparator from '../../utils/comparator'

export default function binarySearch(sortedArr, target, fn) {
  const comparator = new Comparator(fn)

  let start = 0
  let end = sortedArr.length - 1

  while (start <= end) {
    // Вычисляем индекс центрального элемента
    let middle = start + Math.floor((end - start) / 2)

    if (comparator.equal(sortedArr[middle], target)) {
      return middle
    }

    // Если целевое значение меньше центрального элемента
    if (comparator.lessThan(sortedArr[middle], target)) {
      // Переходим к правой половине массива
      start = middle + 1
    } else {
      // Переходим к левой половине массива
      end = middle - 1
    }
  }

  return -1
}

Тестирование


// algorithms/searches/__tests__/binary-search.test.js
import binarySearch from '../binary-search'

describe('binarySearch', () => {
  it('должен найти числа в отсортированных массивах', () => {
    expect(binarySearch([], 1)).toBe(-1)
    expect(binarySearch([1], 1)).toBe(0)
    expect(binarySearch([1, 2], 1)).toBe(0)
    expect(binarySearch([1, 2], 2)).toBe(1)
    expect(binarySearch([1, 5, 10, 12], 1)).toBe(0)
    expect(binarySearch([1, 5, 10, 12, 14, 17, 22, 100], 17)).toBe(5)
    expect(binarySearch([1, 5, 10, 12, 14, 17, 22, 100], 1)).toBe(0)
    expect(binarySearch([1, 5, 10, 12, 14, 17, 22, 100], 100)).toBe(7)
    expect(binarySearch([1, 5, 10, 12, 14, 17, 22, 100], 0)).toBe(-1)
  })

  it('должен найти объекты в отсортированном массиве', () => {
    const sortedArrayOfObjects = [
      { key: 1, value: 'value1' },
      { key: 2, value: 'value2' },
      { key: 3, value: 'value3' },
    ]

    const comparator = (a, b) => {
      if (a.key === b.key) return 0
      return a.key < b.key ? -1 : 1
    }

    expect(binarySearch([], { key: 1 }, comparator)).toBe(-1)
    expect(binarySearch(sortedArrayOfObjects, { key: 4 }, comparator)).toBe(-1)
    expect(binarySearch(sortedArrayOfObjects, { key: 1 }, comparator)).toBe(0)
    expect(binarySearch(sortedArrayOfObjects, { key: 2 }, comparator)).toBe(1)
    expect(binarySearch(sortedArrayOfObjects, { key: 3 }, comparator)).toBe(2)
  })
})

Запускаем тестирование:


npm run test ./algorithms/searches/__tests__/binary-search

Результат:





Такие варианты двоичного поиска предлагают разработчики VSCode:


// https://github.com/microsoft/vscode/blob/main/src/vs/base/common/arrays.ts#L73
export function binarySearch(array, key, comparator) {
    return binarySearch2(array.length, i => comparator(array[i], key));
}

// Не очень понятно, зачем нужна первая функция
export function binarySearch2(length, compareToKey) {
    let low = 0,
        high = length - 1;

    while (low <= high) {
        const mid = ((low + high) / 2) | 0;
        const comp = compareToKey(mid);
        if (comp < 0) {
            low = mid + 1;
        } else if (comp > 0) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    return -(low + 1);
}

// Тоже самое, но в форме одной функции
// https://github.com/microsoft/vscode/blob/main/extensions/html-language-features/server/src/utils/arrays.ts#L60
export function binarySearch(array, key, comparator) {
    let low = 0,
        high = array.length - 1;

    while (low <= high) {
        const mid = ((low + high) / 2) | 0;
        const comp = comparator(array[mid], key);
        if (comp < 0) {
            low = mid + 1;
        } else if (comp > 0) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    return -(low + 1);
}

❯ Интерполяционный поиск


Описание



Интерполяционный (интерполирующий) поиск (interpolation search) основан на принципе поиска в телефонной книге или, например, в словаре. Вместо сравнения каждого элемента с искомым, как при линейном поиске, данный алгоритм производит предсказание местонахождения элемента: поиск происходит подобно двоичному, но вместо деления области поиска на две части, интерполирующий поиск производит оценку новой области поиска по расстоянию между ключом и текущим значением элемента. Другими словами, бинарный поиск учитывает лишь знак разности между ключом и текущим значением, а интерполирующий еще учитывает и модуль этой разности и по данному значению производит предсказание позиции следующего элемента для проверки. Например, если целевое значение ближе к последнему элементу массива, поиск начнется с блока, находящегося в конце массива.


Для поиска целевого значения используется следующая формула:


// Суть формулы - вернуть большее значение `pos`,
// когда искомый элемент ближе к `arr[hi]`, и
// меньшее значение, когда искомый элемент ближе к `arr[lo]`
pos = lo + ((x - arr[lo]) * (hi - lo) / (arr[hi] - arr[Lo]))

arr[] - исходный массив
x - целевое значение
lo - начальный индекс `arr[]`
hi - конечный индекс `arr[]`

В среднем интерполирующий поиск производит log(log(n)) операций, где n — это число элементов исходного массива. Число необходимых операций зависит от равномерности распределения значений среди элементов. В худшем случае (например, когда значения элементов экспоненциально возрастают) интерполяционный поиск может потребовать до O(n) операций.


Реализация


// algorithms/searches/interpolation-search.js
export default function interpolationSearch(sortedArr, target) {
  let start = 0
  let end = sortedArr.length - 1

  while (start <= end) {
    const rangeDelta = sortedArr[end] - sortedArr[start]
    const indexDelta = end - start
    const valueDelta = target - sortedArr[start]

    // Если `valueDelta` равняется `0`, значит, искомый элемент
    // в массиве отсутствует
    if (valueDelta < 0) return -1

    // Если `rangeDelta` равняется `0`, значит, подмассив содержит
    // одинаковые числа, поэтому искать нечего
    if (!rangeDelta) {
      // Это также позволяет избежать деления на 0 при поиске
      // центрального элемента ниже
      return sortedArr[start] === target ? start : -1
    }

    const middleIndex =
      start + Math.floor((valueDelta * indexDelta) / rangeDelta)

    if (sortedArr[middleIndex] === target) {
      return middleIndex
    }

    if (sortedArr[middleIndex] < target) {
      // Переходим к правой половине массива
      start = middleIndex + 1
    } else {
      // переходим к левой половине массива
      end = middleIndex - 1
    }
  }

  return -1
}

Тестирование


// algorithms/searches/__tests/interpolation-search.test.js
import interpolationSearch from '../interpolation-search'

describe('interpolationSearch', () => {
  it('должен найти числа в отсортированных массивах', () => {
    expect(interpolationSearch([], 1)).toBe(-1)
    expect(interpolationSearch([1], 1)).toBe(0)
    expect(interpolationSearch([1], 0)).toBe(-1)
    expect(interpolationSearch([1, 1], 1)).toBe(0)
    expect(interpolationSearch([1, 2], 1)).toBe(0)
    expect(interpolationSearch([1, 2], 2)).toBe(1)
    expect(interpolationSearch([10, 20, 30, 40, 50], 40)).toBe(3)
    expect(
      interpolationSearch(
        [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15],
        14,
      ),
    ).toBe(13)
    expect(
      interpolationSearch(
        [1, 6, 7, 8, 12, 13, 14, 19, 21, 23, 24, 24, 24, 300],
        24,
      ),
    ).toBe(10)
    expect(
      interpolationSearch([1, 2, 3, 700, 800, 1200, 1300, 1400, 1900], 600),
    ).toBe(-1)
    expect(
      interpolationSearch([1, 2, 3, 700, 800, 1200, 1300, 1400, 1900], 1),
    ).toBe(0)
    expect(
      interpolationSearch([1, 2, 3, 700, 800, 1200, 1300, 1400, 1900], 2),
    ).toBe(1)
    expect(
      interpolationSearch([1, 2, 3, 700, 800, 1200, 1300, 1400, 1900], 3),
    ).toBe(2)
    expect(
      interpolationSearch([1, 2, 3, 700, 800, 1200, 1300, 1400, 1900], 700),
    ).toBe(3)
    expect(
      interpolationSearch([1, 2, 3, 700, 800, 1200, 1300, 1400, 1900], 800),
    ).toBe(4)
    expect(
      interpolationSearch([0, 2, 3, 700, 800, 1200, 1300, 1400, 1900], 1200),
    ).toBe(5)
    expect(
      interpolationSearch([1, 2, 3, 700, 800, 1200, 1300, 1400, 19000], 800),
    ).toBe(4)
    expect(interpolationSearch([0, 10, 11, 12, 13, 14, 15], 10)).toBe(1)
  })
})

Запускаем тесты:


npm run test ./algorithms/searches/__tests__/interpolation-search

Результат:





На сегодня это все, друзья. Увидимся в следующей части.



Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩

Комментарии (0)