Algorytm dopasować jeden plik wejściowy z podanych liczb z pliku

miałem wywiad w zeszłym tygodniu. Utknąłem w jednym z pytań w rundzie algorytmicznej. Odpowiedziałem na to pytanie, ale ankieter nie wydawał się przekonany. Właśnie dlatego dzielę to samo.Algorytm dopasować jeden plik wejściowy z podanych liczb z pliku

Proszę powiedzieć mi żadnych zoptymalizowany sposób na to pytanie, tak, że będzie mi pomóc w przyszłych rozmowach.

Pytanie: -

Istnieje 20 pliki tekstowe podane, wszystkie pliki są pliki tekstowe ASCII, posiadające rozmiar mniejszy niż 10^9 bajtów. Podano także jedno wejście, to jest również jeden plik ASCII, powiedzmy, input.txt.

Naszym zadaniem jest strategiczne dopasowanie zawartości tego pliku wejściowego do pliku z podaniem 20 plików i wydrukowanie nazwy najbliższego pasującego pliku. Zawartość pliku wejściowego może być tylko częściowo zgodna:

Z góry dziękuję. Poszukuję miłej odpowiedzi.

Źródło

2013-04-04 devsda

To naprawdę nie jest to możliwe, aby odpowiedzieć w tej formie. Czy pliki te są prawdziwym tekstem, drukowalnym ASCII, podstawowym ASCII lub rozszerzonym ASCII? Czy wynik musi być najlepszym dopasowaniem, czy wystarczającym przybliżeniem? –

Uważam, że istnieje narzędzie systemowe do tego konkretnego celu. 'cmp' Wierzę, że został nazwany. Zgodny z POSIX SO. – yeyo

@Kira Coś mi mówi, że to nie jest to, na co liczył wywiad! – JBentley

je diff i przechodzą przez wc -l lub wdrożyć Levenshtein distance w C++ traktując każdą linię jako pojedynczego znaku (lub innym bardziej odpowiednim jednostka condidering domenę tematu)

Źródło

2013-04-04 19:41:48 bobah

+1, Bardzo dobra odpowiedź, jednak za pomocą algorytmu Edycja odległości jest nieco trudna do zrealizowania (moim zdaniem). – yeyo

@anonim: w dół głosów bez konstruktywnych komentarzy - nie dobrze – bobah

Można tworzyć jakąś indeksowania (na przykład: trie), aby podsumować plik wejściowy. Następnie możesz sprawdzić, ile indeksów pasuje do dokumentów.

Np. Utwórz trie dla pliku wejściowego o długości 10. Dla każdego ciągu o długości 10 (zachodzenie na siebie) w plikach tekstowych sprawdź, ile z nich pasuje do trie.

Źródło

2013-04-04 20:24:49 ElKamina

Używanie trie byłoby nieefektywne, ponieważ rozmiar pliku jest duży, zamiast tego lepszym rozwiązaniem byłoby użycie drzewa B +. –

Jako sugestię do projektowania naprawdę zdolnych, skalowalnych systemów podobieństwa dokumentów, sugeruję przeczytanie rozdziału 3 z Mining Massive Datasets, który jest swobodnie dostępny online. Jednym z przedstawionych tam sposobów jest "gontowanie" zestawów danych poprzez wektoryzację zliczeń słów w zestawy, a następnie mieszanie liczb słów i porównywanie rodzin wyników haszu z podobieństwem Jaccard, aby uzyskać wynik między wszystkimi dokumentami. Może to działać na petabajtach plików z dużą dokładnością, jeśli zostanie to zrobione poprawnie. Wyraźne szczegóły z dobrymi diagramami można odczytać z Stanford's CS246 Slides on Locality Sensitive Hashing. Prostsze podejścia, takie jak zliczanie częstotliwości słów, są również opisane w książce.

Źródło

2013-04-04 21:45:53 Pyrce

Algorytm dopasować jeden plik wejściowy z podanych liczb z pliku

Odpowiedz

Powiązane problemy