Potrzebuję sprytnego algorytmu do indeksowania katalogu ... wskaźników?

Question

Mam katalog muzyki na plikach Ubuntu (.mp3, .wav, itp.). Ten katalog może mieć tyle podkatalogów, ile potrzebuje, bez ograniczeń. Chcę być w stanie dokonać bibliotekę muzyczną z niego - czyli lista powrót piosenek opartych na filtrach:

1) przynależności do playlisty 2) nazwa wykonawcy 3) ciąg wyszukiwania 4) nazwę piosenka itp., itp.

Jeśli jednak nazwy plików zostaną zmienione, przeniesione lub nawet dodane do mojego katalogu muzycznego, muszę być w stanie to odzwierciedlić w moim silniku organizacji muzycznej - szybko!

Początkowo sądziłem, że po prostu monitoruję mój katalog za pomocą pyyotryptu, incronu lub inotify. Niestety mój katalog to udział w Sambie, więc monitoruję zdarzenia plików failed. Moją kolejną myślą było po prostu rekurencyjne przeszukanie katalogu w pythonie i zapełnienie bazy danych SQL. Następnie, podczas aktualizacji, chciałbym po prostu sprawdzić, czy coś się zmieniło (zeskanowanie każdego podfolderu, aby sprawdzić, czy nazwa każdej piosenki jest już w bazie danych, a jeśli nie jest ona dodawana) i odpowiednio dokonać aktualizacji. Niestety, wygląda na to, że jest to fatalna implementacja O(n^2) - okropna dla wielotabajtowej kolekcji muzycznej.

Nieco lepsze może być utworzenie struktury drzewa w SQL, co zawęzi potencjalnych kandydatów do wyszukania dopasowania w dowolnym kroku podfolderu do rozmiaru tego podfolderu. Nadal wydaje się nieelegancki.

Jakie paradygmaty/paczki projektowe mogę wykorzystać, aby pomóc sobie? Oczywiście będzie zawierać wiele sprytnych tabel hash. Po prostu szukam wskazówek w dobrym kierunku, jak podejść do problemu. (Jestem też kompletnym narkomanem do optymalizacji.)

Answer 1

Najtrudniejszą częścią jest skanowanie katalogu, tylko dlatego, że może być kosztowne.

Ale to jest okrutna rzeczywistość, ponieważ nie można używać inotify et al.

W swojej bazie danych, wystarczy utworzyć rekord typu węzła:

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 
) 

To twoja budowa węzła.

Możesz użyć kolumny pełnej ścieżki, aby szybko znaleźć wszystko według bezwzględnej ścieżki.

Gdy plik się rusza, po prostu przelicz ponownie ścieżkę.

Na koniec zeskanuj pliki muzyczne. W systemie Unix możesz zrobić coś takiego:

znaleźć. -type f | sort> sortedListOfFiles

Następnie, po prostu wysysaj wszystkie nazwy ścieżek z bazy danych.

wybierz fullPathName od węzła gdzie = 'd' zamów przez fullPathName

nodeType! Teraz masz dwa posortowaną listę plików.

Przeprowadź je przez DIFF (lub comm), a otrzymasz listę usuniętych i nowych plików. Nie będziesz mieć listy "przeniesionych" plików. Jeśli chcesz przeprowadzić heurystykę w przypadku porównywania nowych i starych plików i mają one te same zakończenia (tzn. ..../album/utwór), aby spróbować wykryć "ruchy" w stosunku do nowych i starych, to dobrze, nic wielkiego. Warto strzelić.

Ale diff da ci różnicę w mgnieniu oka.

Jeśli masz ziliony plików, to przepraszam, to zajmie trochę czasu - ale już wiesz, że kiedy stracisz możliwość inotify. Gdyby tak było, byłaby to tylko przyrostowa konserwacja.

Gdy plik się porusza, znalezienie nowego bezwzględnego ścieżki jest banalne, ponieważ możesz poprosić rodzica o ścieżkę i po prostu dołączyć do niego swoje imię. Potem nie indeksujesz drzewa ani niczego, chyba że chcesz. Działa w obie strony.

Addenda:

Jeśli chcesz śledzić rzeczywiste zmiany nazwy, można uzyskać trochę więcej informacji.

Można to zrobić:

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

-print0 i -0 służą do pracy z plikami ze spacjami w nich. Cytaty w nazwach plików zniszczą to jednak. Lepszym rozwiązaniem może być uruchamianie surowej listy przez pythona i fstat, aby uzyskać i-węzeł. Różne rzeczy, które możesz tutaj zrobić.

To, co to robi, a nie tylko posiadanie imion, również dostanie i-węzeł pliku. I-węzeł jest "prawdziwym" plikiem, katalog łączy nazwy z i-węzłami. W ten sposób można mieć wiele nazw (twarde linki) w systemie plików unix do jednego pliku, wszystkie nazwy wskazują na ten sam i-węzeł.

Po zmianie nazwy pliku, i-węzeł pozostanie bez zmian. W unixie jest jedno polecenie używane do zmiany nazwy i przenoszenia plików, mv. Kiedy mv zmieni nazwę lub przeniesie plik, i-węzeł pozostanie niezmieniony, ZGODNIE Z PLIKIEM JEST W TYM SAMYM SYSTEMIE PLIKÓW.

Używanie i-węzła oraz nazwy pliku pozwoli ci uchwycić trochę bardziej interesujących informacji, takich jak ruchy plików.

Nie pomoże, jeśli usunie plik i doda nowy plik. Ale BĘDZIESZ (prawdopodobnie) będziesz w stanie powiedzieć, że to się stało, ponieważ jest mało prawdopodobne, aby stary i-węzeł został ponownie użyty dla nowego i-węzła.

Więc jeśli masz listę plików (sortowane według nazwy pliku):

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

i ktoś usuwa i dodaje z powrotem piosenkę 2, będziesz miał coś podobnego

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

ale jeśli

mv song1.mp3 song4.mp3 

Dostaniesz::

to zrobić

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

Innym zastrzeżeniem jest to, że w przypadku utraty dysku i przywrócenia go z kopii zapasowej, prawdopodobne jest, że wszystkie i-węzły ulegną zmianie, skutecznie wymuszając przebudowę indeksu.

Jeśli jesteś prawdziwym poszukiwaczem przygód, możesz spróbować grać z rozszerzonymi atrybutami systemu plików i przypisać inne ciekawe meta dane do plików. Nie zrobiłem z tym większego problemu, ale są również możliwości, i są prawdopodobnie niewidoczne niebezpieczeństwa, ale ...

Answer 2

Rzeczywistość jest, jest to problem twardy. Zaczynasz także od wad: Python i mySQL nie są najszybszymi narzędziami do tego celu.

Nawet na iTunes skarżą się ze względu na czas potrzebny na import bibliotek i indeksowanie nowych plików. Czy potrafisz sobie wyobrazić godziny pracy, które stały się tak dobre, jak iTunes?

Najprościej jest, aby spojrzeć na kod dużych open source odtwarzaczy muzycznych takich jak

• Miro, http://www.getmiro.com/,
• Banshee, http://banshee.fm/ i
• Songbird http://getsongbird.com/

Spróbuj dopasować swoje algorytmy do swoich celów i do idiomów Pythona.

Answer 3

mój aggregate_digup program czyta rozszerzony plik w formacie sha1sum.txt wyprodukowany przez program digup. to pozwala mi zlokalizować plik na podstawie jego sumy sha1. program digup przechowuje w swoim pliku wyjściowym skrót hasłowy mtime i ścieżkę. domyślnie pomija hashing pliku, jeśli mtime i rozmiar pasują. Indeks utworzony przez mój aggregate_digup jest używany przez moją zmodyfikowaną wersję otwartego menu kontekstowego wtyczki gedit, pozwalającą na jedno kliknięcie opcji na sha1:b7d67986e54f852de25e2d803472f31fb53184d5, a wyświetli kopie pliku, o którym wie, więc możesz wybrać jedną i otworzyć ją.

jak to się wiąże z problemem jest to, że są dwie części: jedna listy odtwarzania i dwa pliki.

jeśli możemy założyć, że nic, co gracz robi, zmienia pliki, wtedy skrót i rozmiary plików są stałe. więc powinniśmy być w stanie użyć rozmiaru i skrótu pliku jako unikalnego identyfikatora.

na przykład klucz do pliku wymienić: 222415:b7d67986e54f852de25e2d803472f31fb53184d5

Odkryłam, że w praktyce nie ma kolizji w każdej naturalnej kolekcji.

(to znaczy, że metadane ID3, który jest dołączony lub dołączany do danych mp3 nie można zmienić, jeśli nie pominąć, że metadane podczas mieszania)

więc baza playlist byłoby coś to:

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

zaktualizować tabelę pliki:

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 4

import os 
import re 

swoje inny kod tutaj, że początkowo konfiguruje dictonary zawierający pliki, które mają już w swojej bibliotece (Zadzwoniłem słownika 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. 

Można użyć tego kodu jako mały funkcji lub cokolwiek i wezwać go na dowolnej rozdzielczości czasowej chciałbyś. Użyje polecenia find i odnajdzie każdy nowo utworzony plik w ciągu ostatniego dnia.Następnie sprawdzi, czy jest on typu music_type, czy to sprawdzi nazwę pliku względem bieżącej bazy danych, którą skonfigurowałeś i będziesz mógł kontynuować przetwarzanie stamtąd. To powinno być w stanie przygotować Cię do aktualizacji nowo dodanej muzyki lub czegokolwiek innego.

Answer 5

Zrobiłem coś podobnego w przeszłości, ale skończyło się na wykorzystaniu Amaroka w/MySQL. Amarok utworzy dla ciebie bazę danych mysql i całkiem dobrze indeksuje wszystkie twoje pliki - po tym połączenie z bazą danych powinno być stosunkowo proste z Pythona.

To było dość oszczędność czasu dla mnie :)

HTH