Я хочу умный алгоритм для индексации файлового каталога ... указатели?

Question

У меня есть каталог музыки в файлах Ubuntu (.mp3, .wav и т. Д.). Этот каталог может иметь столько подкаталогов, сколько ему нужно, без ограничений. Я хочу иметь возможность сделать из него музыкальную библиотеку, то есть вернуть список песен на основе фильтров:

1) членство в плейлисте 2) имя исполнителя 3) поиск строки 4) название песни и т. д.

Однако, если имена файлов изменяются, перемещаются или даже добавляются в мой каталог Music, я должен иметь возможность отразить это в моем механизме организации музыки - быстро!

Первоначально я думал просто отслеживать мой каталог с помощью pyinotify, incron или inotify. К сожалению, мой каталог - это общий ресурс Samba, поэтому мониторинг файловых событий не удалось . Поэтому я предпочел просто рекурсивно искать каталог в python и заполнять базу данных SQL. Затем при обновлении я просто посмотрел бы, изменилось ли что-нибудь (просматривая каждую подпапку, чтобы увидеть, есть ли название каждой песни в базе данных, и если не добавлял ее), и соответственно сделал UPDATE. К сожалению, это кажется ужасной O(n^2) реализацией - ужасно для мульти-терабайтной музыкальной коллекции.

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

Какие парадигмы / пакеты дизайна я могу использовать, чтобы помочь себе? Очевидно, будет задействовано много умных хеш-таблиц. Я просто ищу указатели в правильном направлении, как подходить к проблеме. (Также я полный наркоман для оптимизации.)

Answer 1

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

Но это жестокая реальность, поскольку вы не можете использовать inotify и др.

Вв вашей базе данных просто создайте запись типа узла:

create table node (
    nodeKey integer not null primary key,
    parentNode integer references node(nodeKey), // allow null for the root, or have root point to itself, whatever
    fullPathName varchar(2048),
    nodeName varchar(2048),
    nodeType varchar(1) // d = directory, f = file, or whatever else you want
)

Это структура вашего узла.

Вы можете использовать столбец полного пути, чтобы быстро найти что-либо по абсолютному пути.

Когда файл перемещается, просто пересчитайте путь.

Наконец, просканируйте свои музыкальные файлы.В Unix вы можете сделать что-то вроде:

find.тип F |sort> sortedListOfFiles

Далее просто высосите все пути из базы данных.

выберите fullPathName из узла, где nodeType! = 'd', упорядочьте по fullPathName

сейчасу вас есть два отсортированных списка файлов.

Запустите их через DIFF (или comm), и вы получите список удаленных и новых файлов.У вас не будет списка «перемещенных» файлов.Если вы хотите провести эвристический анализ, сравнивая новые и старые файлы с одинаковыми окончаниями (т. Е. .... / альбом / песня), чтобы попытаться обнаружить «ходы» по сравнению с новым и старым, тогда ничего страшного.Стоит попробовать.

Но diff даст вам ваш дифференциал в одно мгновение.

Если у вас есть миллионы файлов, тогда, извините, это займет некоторое время - но вы ужеЗнайте, что когда вы потеряете способность inotify.Если бы у вас было это, это было бы просто добавочным обслуживанием.

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

Дополнения:

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

Вы можете сделать это:

find . -type f -print0 | xargs -0 ls -i | sort -n > sortedListOfFileWithInode

-print0 и -0 используются для работы с файлами с пробелами в них.Кавычки в именах файлов разрушат это однако.Возможно, вам лучше запустить необработанный список через python и fstat, чтобы получить индекс.Здесь вы можете делать разные вещи.

Вместо того, чтобы просто иметь имена, вы также получаете индекс файла.Inode - это «настоящий» файл, каталог связывает имена с inode.Таким образом, вы можете иметь несколько имен (жестких ссылок) в файловой системе Unix на один файл, все имена указывают на один и тот же индекс.

Когда файл переименовывается, индекс остается неизменным.,В Unix есть единственная команда, используемая для переименования и перемещения файлов, mv.Когда mv переименовывает или перемещает файл, индекс остается таким же длинным, как и файл в той же системе файлов.

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

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

Так что если у вас есть список файлов (отсортированный по имени файла):

1234 song1.mp3
1235 song2.mp3
1236 song3.mp3

и кто-то удаляет и добавляет обратно песню 2, у вас будет что-то вроде

1234 song1.mp3
1237 song2.mp3
1236 song3.mp3

Но если вы сделаете это:

mv song1.mp3 song4.mp3

ВыВы получите:

1237 song2.mp3
1236 song3.mp3
1234 song4.mp3

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

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

Answer 2

my aggregate_digup программа читает расширенный файл формата sha1sum.txt, созданный программой digup .это позволяет мне найти файл на основе его sha1sum.программа digup хранит хэш размера mtime и путь к нему в своих выходных данных.по умолчанию он пропускает хэширование файла, если mtime и size совпадают.индекс, созданный моим aggregate_digup, используется моей модифицированной версией плагина gedit для контекстного меню open uri, позволяющего выбрать опцию sha1:b7d67986e54f852de25e2d803472f31fb53184d5, и в нем будут перечислены копии файла, о которых он знает, чтобы вы могли выбрать один и открыть его.

как это связано с проблемой, состоит в том, что есть две части: один список воспроизведения и два файла.

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

например ключ для упомянутого файла: 222415:b7d67986e54f852de25e2d803472f31fb53184d5

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

(это означает, что метаданные ID3, добавляемые или добавляемые к данным mp3, не могут измениться, если вы не пропустите эти метаданные во время хеширования)

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

files(file_key, hash, size, mtime, path, flag)
tracks(file_key, title, artist)
playlists(playlistid, index, file_key)

, чтобы обновить таблицу файлов:

import os
import stat
# add new files:
update files set flag=0
for path in filesystem:
    s=os.stat(path)
    if stat.S_ISREG(s.st_mode):
        fetch first row of select mtime, hash, size from files where path=path
        if row is not None:
            if s.st_mtime == mtime and s.st_size == size:
                update files set flag=1 where path=path
                continue
        hash=hash_file(path)
        file_key="%s:%s" % (int(s.st_mtime), hash)
        insert or update files set file_key=file_key, size=s.st_size, mtime=s.st_mtime, hash=hash, flag=1 where path=path
# remove non-existent files:
delete from files where flag=0

Answer 3

Реальность такова, что это сложная проблема.Вы также начинаете с недостатка: Python и mySQL - не самые быстрые инструменты для этой цели.

Даже на iTunes жалуются из-за времени, которое требуется для импорта библиотек и индексирования новых файлов.Можете ли вы представить, сколько человеко-часов потратили на то, чтобы сделать iTunes таким, каким он есть?

Лучше всего взглянуть на код основных музыкальных плееров с открытым исходным кодом, таких как

• Miro., http://www.getmiro.com/,
• Банши, http://banshee.fm/, и
• Songbird, http://getsongbird.com/

И попробуйте адаптировать свои алгоритмы к вашей цели и кPython идиомы.

Answer 4

В прошлом я делал нечто подобное, но в итоге использовал Amarok с MySQL. Amarok создаст для вас базу данных mysql и довольно хорошо проиндексирует все ваши файлы - после этого взаимодействие с базой данных должно быть относительно простым с python.

Это сэкономило мне время :) 1003 *

НТН

Answer 5

import os
import re

ваш другой код здесь, который изначально устанавливает диктонар, содержащий файлы, которые у вас уже есть в вашей библиотеке (я назвал словарь archived_music)

music_directory = '/home/username/music'
music_type = '\.mp3$|\.wav$|\.etc$'
found_files = os.popen('find %s -type f -mtime 1 2>/dev/null' % music_directory)
for file in found_files:
    directory, filename = os.path.split()
    if re.compile(music_type).search(filename):
        #found a music file, check if you already have it in the library
        if filename in archived_music:
            continue
        #if you have gotten to this point, the music was not found in the arcchived music directory, so now perform whatever processing you would like to do on the full path found in file.

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