Как удалить повторяющиеся строки текста в JavaScript

Чтобы удалить повторяющиеся строки в JavaScript, разбейте текст по /\r?\n/, пропустите строки через Set и снова соедините их: [...new Set(text.split(/\r?\n/))].join('\n').

Это может понадобиться при очистке списка email-адресов или идентификаторов перед массовым импортом, при наведении порядка в лог-файле, при объединении двух CSV-выгрузок или при удалении повторов из списка слов. Однострочник справляется с точными дубликатами, а инструмент для удаления повторяющихся строк сделает это прямо в браузере, если вам нужен только результат. Для почти-дубликатов, которые отличаются лишь регистром, пробельными символами, окончаниями строк или пустыми строками, в статье приведена готовая к копированию функция с выбором стратегии: побеждает первое или последнее вхождение.

Однострочник для удаления повторяющихся строк в JavaScript

Самый короткий способ удалить повторяющиеся строки в JavaScript — поставить Set между split и join:

const dedupeLines = (text) => [...new Set(text.split(/\r?\n/))].join('\n');

dedupeLines('one\nthree\ntwo\nthree\none');
// 'one\nthree\ntwo'

Это работает, потому что Set перебирает свои значения в порядке добавления. Каждая строка остаётся на позиции своего первого вхождения, а последующие копии отбрасываются. Этот порядок определён спецификацией ES2015: add добавляет каждое новое значение в конец внутреннего списка множества. Для чистых, сгенерированных машиной входных данных больше ничего не нужно. Остальные возможности API Set описаны в руководстве по методам Set в JavaScript.

Где наивная версия с Set даёт сбой?

Set сравнивает строки точно (по алгоритму SameValueZero), поэтому разница даже в один символ делает две строки различными. В каждом из примеров ниже остаётся строка, которую вы, скорее всего, хотели удалить:

• Регистр: в 'Apple\napple' остаются обе строки.
• Пробелы в конце строки: в 'apple \napple' остаются обе строки, потому что одна из них заканчивается пробелом.
• Окончания строк CRLF: 'apple\r\napple'.split('\n') даёт ['apple\r', 'apple']. Разбиение только по '\n' оставляет \r в конце каждой строки, кроме последней, если после неё нет перевода строки, поэтому последняя строка никогда не совпадёт со своими более ранними копиями. Это исправляет регулярное выражение в качестве разделителя в split — /\r?\n/. Если ожидается текст с окончаниями строк классической Mac OS (одиночный \r), используйте /\r\n|\r|\n/.
• Пустые строки: 'a\n\nb\n\nc' превращается в 'a\n\nb\nc'. Вторая пустая строка считается дубликатом первой, поэтому абзацы b и c сливаются.
• Завершающий перевод строки: 'a\n\nb\n' превращается в 'a\n\nb'. Пустая строка после последнего перевода строки совпадает с более ранней пустой строкой и удаляется.

Избегайте lines.filter((l, i, a) => a.indexOf(l) === i). indexOf выполняет линейный поиск по массиву, поэтому вызов для каждой строки делает весь проход O(n²). Спецификация требует, чтобы поиск в Set в среднем был быстрее линейного, так что Set избавляет от повторного сканирования. У обычного объекта в роли списка просмотренных значений свои проблемы: строка __proto__ или hasOwnProperty может его сломать.

Удаляйте дубликаты по нормализованному ключу, выводите исходную строку

Чтобы считать почти-дубликаты равными, проверяйте по Set нормализованный ключ (обрезанную строку, приведённую к нижнему регистру, если нужно сравнение без учёта регистра), а в результат добавляйте исходную строку.

function removeDuplicateLines(text, options = {}) {
  const {
    caseSensitive = true,
    trim = true,
    collapseWhitespace = false,
    blankLines = 'collapse', // 'keep' | 'collapse' | 'remove'
  } = options;

  const eol = text.includes('\r\n') ? '\r\n' : '\n';
  const trailingNewline = /\r?\n$/.test(text);
  const lines = text.replace(/\r?\n$/, '').split(/\r?\n/);

  const toKey = (line) => {
    let key = trim ? line.trim() : line;
    if (collapseWhitespace) key = key.replace(/\s+/g, ' ');
    return caseSensitive ? key : key.toLowerCase();
  };

  const isBlank = (line) => line.trim() === '';
  const seen = new Set();
  const out = [];

  for (const line of lines) {
    if (isBlank(line)) {
      if (blankLines === 'remove') continue;
      if (blankLines === 'collapse' && out.length && isBlank(out[out.length - 1])) continue;
      out.push(line);
      continue;
    }
    const key = toKey(line);
    if (seen.has(key)) continue;
    seen.add(key);
    out.push(line);
  }

  return out.join(eol) + (trailingNewline ? eol : '');
}

removeDuplicateLines('Apple\napple \n\n\nbanana\nBanana\n', { caseSensitive: false });
// 'Apple\n\nbanana\n'

Как работают параметры removeDuplicateLines:

• trim использует String.prototype.trim, который также удаляет неразрывные пробелы и начальный BOM. В выводе сохраняются исходные отступы.
• caseSensitive: false использует toLowerCase, который даёт одинаковый результат в любой локали.
• blankLines: 'keep' исключает пустые строки из дедупликации, и они остаются на своих местах. 'collapse' превращает каждую последовательность пустых строк в одну; проверяется последняя строка вывода, поэтому две пустые строки, между которыми был удалённый дубликат, тоже схлопываются. 'remove' удаляет все пустые строки.
• Функция сохраняет завершающий перевод строки исходного текста. Если во входных данных встречается хотя бы один \r\n, в выводе \r\n используется для всех строк. Для файлов со смешанными окончаниями строк это упрощение.

Map из ключа в строку работает так же: if (!map.has(key)) map.set(key, line). О том, когда какая структура подходит, читайте в статье Map vs Set vs Object. Нормализация Unicode, «умные» кавычки и другие артефакты вставки — это отдельный этап, которому посвящена статья Cleaning Up Text People Paste Into Your App.

Первое или последнее вхождение

При удалении повторяющихся строк сохранение первого и последнего вхождения даёт разный результат. К тому же у сохранения последнего вхождения есть два варианта, различающихся порядком. Для входных данных ['apple', 'banana', 'Apple', 'cherry'] при сравнении без учёта регистра:

function keepLast(lines, toKey = (l) => l.trim().toLowerCase(), { moveToEnd = true } = {}) {
  const byKey = new Map();
  for (const line of lines) {
    const key = toKey(line);
    if (moveToEnd) byKey.delete(key);
    byKey.set(key, line);
  }
  return [...byKey.values()];
}

Map хранит ключи в порядке их первого добавления, а вызов set() для уже имеющегося ключа меняет значение, не перемещая ключ. Поэтому проход, который только перезаписывает значения, возвращает последнюю версию каждой строки, но на позиции её первого появления. Чтобы поместить каждую строку туда, где она встретилась в последний раз, вызывайте delete(key) перед set(key, line) — тогда ключ будет заново добавлен в конец.

Удаление повторяющихся строк из больших файлов в терминале

Для файлов, которые слишком велики, чтобы вставлять их целиком, удаляйте повторяющиеся строки в командной оболочке с помощью sort -u или awk. sort -u удаляет дубликаты через сортировку, поэтому исходный порядок теряется. Кроме того, строки сравниваются по правилам сортировки (collation) текущей локали, что в локалях, отличных от C, может приводить к слиянию строк, которые не совпадают побайтово. Для точного сравнения используйте LC_ALL=C sort -u.

awk '!seen[$0]++' выводит каждую строку при её первом появлении и сохраняет порядок входных данных, но хранит каждую уникальную строку в ассоциативном массиве в памяти. awk '!seen[tolower($0)]++' игнорирует регистр. В файлах с CRLF символ \r попадает в обработку обоих инструментов, поэтому сначала удалите его с помощью tr -d '\r'.

LC_ALL=C sort -u input.txt > output.txt
awk '!seen[$0]++' input.txt > output.txt
tr -d '\r' < input.txt | awk '!seen[$0]++' > output.txt

Заключение

Для точных дубликатов используйте new Set. Если входные данные поступают от людей или из нескольких источников, удаляйте дубликаты по нормализованному ключу и выводите исходную строку. Выбирайте политику обработки пустых строк и правило «побеждает первое» или «побеждает последнее» осознанно, а не полагайтесь на значения по умолчанию. Скопируйте removeDuplicateLines, настройте параметры под свои данные, а если нужно не удалять связанные строки, а группировать их, используйте Object.groupBy.

Часто задаваемые вопросы

Как в JavaScript оставить только строки, которые встречаются ровно один раз?

Сначала подсчитайте вхождения, затем отфильтруйте. За один проход постройте Map, сопоставляющий строку с количеством её вхождений, а затем оставьте строки с количеством 1: lines.filter((line) => counts.get(line) === 1). Это не дедупликация, при которой сохраняется одна копия каждой повторяющейся строки. Здесь любая строка, встречающаяся два раза и более, удаляется полностью. Если почти-дубликаты должны считаться одной строкой, ведите подсчёт по нормализованному ключу.

Как удалить из одного списка строки, которые уже есть в другом списке?

Загрузите второй список в Set, а затем отфильтруйте по нему первый список: const exclude = new Set(listB); listA.filter((line) => !exclude.has(line)). Каждая проверка — это поиск в Set, поэтому вы избегаете квадратичной сложности вызова includes или indexOf по массиву для каждой строки. Предварительно разбейте оба текста по /\r?\n/ и примените к обеим сторонам одинаковый ключ с trim или приведением к нижнему регистру.

Почему две на вид одинаковые строки остаются после дедупликации?

Обычно они содержат разные кодовые точки Unicode. Буква с диакритикой, например é, может храниться как один предкомпонованный символ или как обычная e, за которой следует комбинируемый диакритический знак. Set сравнивает кодовые единицы точно, поэтому считает такие строки разными. Чтобы они совпадали, добавьте line.normalize('NFC') в функцию построения ключа. trim не удаляет пробелы нулевой ширины (U+200B), поэтому их нужно удалять отдельно.

Как удалить повторяющиеся строки из большого файла в Node.js, не загружая весь файл в строку?

Читайте файл потоково с помощью модуля node:readline и проверяйте каждую строку по Set. Создайте интерфейс через createInterface({ input: createReadStream(path), crlfDelay: Infinity }), перебирайте его в цикле for await и записывайте строку, только если её ещё нет в Set. Параметр crlfDelay: Infinity заставляет readline воспринимать каждую последовательность CRLF как один перевод строки. Как и в случае с awk, потребление памяти всё равно растёт с количеством уникальных строк.