Поиск частых подстрок в списке строк

Например: название книги, номер страницы, кто сканировал, откуда скачано, к какой дате приурочена выкладка, и т.п. Формат произвольный.

«Playboy-69_228_20200202.png»?

Формат произвольный.

«20200202_227_Playboy-69.png»?

Ну разбивай тогда на части

from collections import Counter, defaultdict
cnt = Counter()
filedb = defaultdict(list)
...
for word in filename.split('_'):
  cnt[word] += 1
  filedb[word].append(filename)

А там уже сам гадай что есть имя, что название книги…

С точностью - никак. Ты задал вопрос из разряда упорядочивания бесконечности. Математически - это расходящтеся ряды. Из практики тебе нужны алгоритмы fuzzy, посмотри тут куча дискуссий на эту тему. Ну а с точки зрения логики, ты пытаешься решить административную задачу техническими средствами => нет пути.

Ну разбивай тогда на части

Названия обычно состоят из нескольких слов. Как сохранить их порядок?

P.S. А для разбиения на слова, пожалуй, удобнее re.split().

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

 < input | sort | uniq -c | sort -gr 

Если их всего несколько тысяч, то быстрее всего будет mc. Выделяешь, например, файлы по маске Playboy и копируешь в отдельную директорию. Потом Hustler и так далее. Это и есть одна из задач, где двухпанельники удобнее всего.

*Playboy*

69

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

Можно не ручками. Можно забить в реляционную БД:

• Список имён.
• Список токенов.
• Отношение многие-ко-многим между токенами и именами.

А дальше можно обращаться к этой БД, получая какие угодно сочетания токенов и имён.

с алгоритмической точки зрения, надо построить индекс вроде суффиксного дерева или суффиксного массива, и искать по нему. Тогда для любой подстроки можно будет узнать за константное или логарифмическое время, в каком числе строк она встречается.

Вот например либа на питоне https://github.com/intsights/pysubstringsearch - api не совсем нужное, но вроде должно работать достаточно быстро, в README ее тестируют на файле в 7.5 гигов

Требуется разбить их на группы

Вообще это задача кластеризации из математической статистики.

Как сделать быстро?

В смысле потратить мало твоего времени, или чтобы мало работал компьютер? Если первое, то никак.

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

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

Как задавать последовательности слов, чтобы считало их частоты? Например, [«Red», «Shoe»], [«Red», «Rain»] и [«Limited», «time», «Red», Offer"]. Число слов в последовательности может быть произвольным.

мало твоего времени, или чтобы мало работал компьютер?

Вопрос задал после того, как компьютер за 8 часов обработал около 2% массива.

несколько тысяч

«Несколько» ближе к 100, чем к 1.

разбить имена на токены

Как выделять повторяющиеся токены? Если разбивать на слова, как выбирать последовательности слов? Если перебирать по букве, получается слишком долго.

Чем ваша новая задача принципиально отличается от вашей же задачи про поиск похожих картинок?

Подход похожий и уже дали направление - токены, эмбеддинги и сравнение векторов.

Почитайте, как ЧатГПТ в этом плане работает - Stephen Wolfram всё раскладывает по полочкам про ChatGPT

Список имён.
Список токенов.
Отношение многие-ко-многим между токенами и именами.

А дальше можно обращаться к этой БД, получая какие угодно сочетания токенов и имён.

100 тысяч имён. В каждом по 5-8 слов-токенов. (Из которых самое частое — «png».) Будет ли выгода, если как-то учесть порядок следования токенов в имени?

Чем ваша новая задача принципиально отличается от вашей же задачи про поиск похожих картинок?

Сравнение картинок отложил до покупки новой видеокарты. Все рекомендованные в той теме библиотеки на одном процессоре удручающе медленно работают.

Кмк, новый подход с поиском подстрок будет не сильно меннее трудозатратным.

Для отсканированных текстов сравнение картинок не работает вообще. Две стены текста оказываются похожими, если совпадает усреднённая яркость.

https://github.com/intsights/pysubstringsearch

Спасибо, попробую.

Это, конечно, интересное замечание, но в той теме все поняли, что речь идёт не про сканы текстов, а про фотки-картинки.

Пробовала однажды easy file organizer, мне не понравилось, но вроде бы подходит. Возни с ним много.

Будет ли выгода, если как-то учесть порядок следования токенов в имени?

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

Как задавать последовательности слов, чтобы считало их частоты? Например, [«Red», «Shoe»], [«Red», «Rain»] и [«Limited», «time», «Red», Offer"]. Число слов в последовательности может быть произвольным.

Ну вы же сами себе и ответили, если у вас произвольное число слов в последовательности и есть файлы

RedShoe.jpg
Red_Rain.jpg
Limited-time.RedOffer.png

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

А потом уже, когда устанете делить на токены, то имея список токенов, к каждому токену искать список файлов в которых этот токен есть, а потом уже смотреть у каких файлов 2 общих токена, каких 1 общий токен например, и т.д и на основе общих токенов группировать файлы.

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

Советую импортировать все имена файлов в SQL(реляционную) базу данных и дальше обрабатывать с помощью языка SQL. Python также применим к данным из SQL-БД.

там имена (без расширения) разбиваются на части. разделитель можно заменить на «-». в cnt содержится количество слов, а в filedb: «слово» => [«название-файла-где-встречается-слово.what», «еще-файл-где-содержится-слово.what»]. нужно просто посмотреть какой мусор и сколько раз встречается, а потом его вырезать из имени, превращая имя в название папки (например, сразу можно вырезать числа re.sub(r'\d+','',filename))

Из которых самое частое — «png».

>>> import os.path
>>> os.path.splitext('Penis-Konina.png')
('Penis-Konina', '.png')
>>> basename, _ = os.path.splitext('Penis-Konina.png')
>>> basename
'Penis-Konina'

раскидай по dict али Counter используя в качестве ключа группирующее значение

у меня такое смутное ощущение, что у многих отписавшихся систематическое образование скажем так затуманено :-)

то что запрашивает ТС называется префиксное дерево и строится алгоритмом Хаффмана (и его вариациями), даже без разбиений на токены.

зато тебе твое незамутненное систематическое образование мешает видеть простые решения (и префиксное дерево тут ненужно-с)

Я бы построил обратный индекс из n-грамм. Далее, анализируя этот индекс можно строить любую статистику. Кажется, это стандартное решение для такого класса задач.

Префиксное дерево строится алгоритмом Хаффмана? Что-то ты не то курил. Или дай ссылку чего ты имел ввиду, развей плиз туман нашего «систематического» образования.

Вообще, если в эту сторону копать, то наверное больше подошло бы сравнение с алгоритмом построения BPE (byte-pair encoding). Принцип «в цикле объединять два самых частых токена» вполне может быть использован для решения задачи топикстартера.

Вот что говорит GPT-4:

Одним из подходов для решения этой проблемы может быть применение алгоритма, который используется для извлечения наиболее часто встречающихся слов или фраз из коллекции текстов, таких как TF-IDF (Term Frequency-Inverse Document Frequency) или их аналогов. Однако, эти подходы могут не всегда работать идеально в случае с именами файлов, которые имеют конкретные форматы и могут включать специфические символы.

В вашем случае может быть полезно использовать Byte Pair Encoding (BPE) или аналогичный алгоритм. Сначала вы можете поделить имена файлов на отдельные слова или символы, а затем последовательно объединять наиболее часто встречающиеся пары символов или слов, создавая словарь из «токенов». Эти токены могут представлять собой названия книг, если они часто встречаются в именах файлов.

Здесь пример реализации такого подхода:

import collections
import re

def get_stats(vocab):
    pairs = collections.defaultdict(int)
    for word, freq in vocab.items():
        symbols = word.split()
        for i in range(len(symbols)-1):
            pairs[symbols[i],symbols[i+1]] += freq
    return pairs

def merge_vocab(pair, v_in):
    v_out = {}
    bigram = re.escape(' '.join(pair))
    p = re.compile(r'(?<!\S)' + bigram + r'(?!\S)')
    for word in v_in:
        w_out = p.sub(''.join(pair), word)
        v_out[w_out] = v_in[word]
    return v_out

def get_vocab(filenames):
    vocab = collections.defaultdict(int)
    for name in filenames:
        words = name.strip().split()
        for word in words:
            vocab[' '.join(word)] += 1
    return vocab

# this is your list of file names
filenames = [...]  

vocab = get_vocab(filenames)

num_merges = 10  # hyperparameter, you could tune this value for your task
for i in range(num_merges):
    pairs = get_stats(vocab)
    if not pairs:
        break
    best = max(pairs, key=pairs.get)
    vocab = merge_vocab(best, vocab)

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

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

BPE на самом деле скорее всего оверкилл, решение с n-gram’ами слов, как предложил urxvt Поиск частых подстрок в списке строк (комментарий), будет гораздо проще

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

Советую импортировать все имена файлов в SQL(реляционную) базу данных и дальше обрабатывать с помощью языка SQL. Python также применим к данным из SQL-БД.

Как резать стринги на токены средствами SQL?

В той теме о нейросетях речь не шла.

Тоже самое, но написанное человеком:

from collections import Counter, defaultdict
phrase_counter = Counter()
phrase_filenames = defaultdict(list)
# ...
for filename in ['228с Путешествие из Москвы в Санкт-Петерубург Пушкин С.А.png']:
  basename=filename[:filename.rfind('.')]
  words=basename.split()
  for i in range(len(words) - 1):
      for j in range(i + 1, len(words)):
              phrase=" ".join(words[i:j])
              phrase_counter[phrase]+=1
              phrase_filenames[phrase].append(filename)
#phrase_counter.most_common(10)
# а в phrase_filenames имена файлов, где сочетание слов встречается

Код, сгенерированный чмоgpt - просто мусор какой-то

резюме: оно заменит программиздов примерно никогда, но как поисковик кусков кода на гитхабе подходило бы, если доступ к таким «высоким» технологиям не был забанен для россии

Вы можете разрезать стринги на токены через функцию Substring_index для mysql. Или можно разрезать их в императивном коде python-на перед помещением в БД или после. К примеру создать ещё одну таблицу tokens с полями token1, token2…tokenN.

Просто по опыту, та обработка данных которая в пайтоне занимает десяток строк в SQL будет одним коротким запросом. Кроме того, данные в РСУБД не теряются, все промежуточные данные можно сохранять в таблицах через select into.

’ ’.join(word)

Зачем добавлять пробелы между буквами?