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

Question

Контекст:
Я создаю программу, которая будет сортировать и переименовывать мои медиа-файлы, которые называются, например. The.Office.s04e03.DIVX.WaREZKiNG.avi в организованную структуру папок, которая будет состоять из списка папок для каждого сериала, каждая папка будет иметь список папок для сезонов, и эти папки будут содержать мультимедийные файлы.

Проблема: Я не уверен в том, что лучший метод для чтения имени файла и определения, какая часть этого имени является телешоу. Например, В "The.Office.s04e03.DIVX.WaREZKiNG.avi" The Office - название серии. Я решил иметь список всех телепередач и проверить, является ли каждая телепередача подстрокой в ​​имени файла, но, насколько я знаю, это означает, что мне нужно проверять каждую серию по названию каждого файла.

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

Спасибо

Answer 1

Это зависит от общей структуры имен файлов в целом, например, всегда ли сначала имя серии? Если так, то древовидная структура хорошо работает. Есть ли стандартная маркировка между словами (точка в вашем примере), если вы можете разделить строку на них и создать независимую от регистра хеш-таблицу интересных слов для повышения производительности.

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

Answer 2

Алгоритм Aho-Corsasick [1] эффективно решает проблему «действительно ли эта длинная строка точно содержит любую из этих коротких строк».

Однако я подозреваю, что это не та проблема, которую вы хотитерешать.Мне кажется, что вы хотите что-то извлечь вероятные компоненты из строки, которая находится в одном из, возможно, многих различных форматов.Я подозреваю, что наличие нескольких различных регулярных выражений для возможных поставщиков, видеоформатов, маркеров сезона / эпизода, возможно, базы данных названий шоу и т. Д., Действительно то, что вам нужно.Затем вы можете независимо запускать эти разные «экстракторы информации» для ваших имен файлов, чтобы вытащить их структуру.

[1] http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm