Haskell: обнаружение изменений в неконтролируемом CSV-файле

Question

Я разрабатываю приложение, которое будет считывать данные с нуля или более файлов CSV, которые я буду называть «внешними» данными. Приложение будет поддерживать производные («внутренние») данные в своих собственных (SQLite) таблицах, связанных с «строками» (строками) во внешних данных, чтобы пользователь мог вставлять, удалять или изменять строки, а полученные данные все равно будут связанных с одной и той же строкой. Если внешние данные были таблицей Postgres, я мог бы использовать OID строки, чтобы связать/соединить «внешний» с «внутренними» данными. Существует соответствие 1: 1 между внутренними и внешними строками.

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

Теперь это немного эвристически, но, как я уже сказал, я хотел бы обнаружить CRUD во внешнем CSV, поэтому я думал, что нужно вычислить 256-битный CRC-отпечаток для каждой внешней строки, и сохраните это во внутренней таблице SQLite. Затем, когда приложение запускается, оно имеет как внутренний, так и внешний [Integer], который может сравниться как программа GNU/Unix/Linux diff для обнаружения незначительных изменений во внешнем файле. Мне нужны две отдельные таблицы: я хочу разрешить пользователям поставлять «внешний» CSV и изменять его, но я хочу контролировать, что находится во внутренней таблице.

Я ожидаю, что внешние данные будут иметь порядок нескольких сотен строк; скажем, 1000 не более.

Итак, мой вопрос: есть ли библиотека, которая бы эвристически сравнивала два отпечатка пальца [Integer] и выводит минимальный список различий с точки зрения добавления, удаления и изменения? или что-нибудь в этом направлении?

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

Answer 1

Мой совет: не беспокойтесь отпечатки пальцев. Используйте пакет Diff; вы можете указать стоимость для любого изменения одной записи, и она найдет минимальное изменение стоимости (с учетом обычных ограничений на diff: без повторного заказа и т. д.).

Если вы хотите поддерживать переупорядочение, вы теряете эффективность в больших количествах, но это все еще можно сделать.