算法將一個輸入文件與給定數量的文件相匹配

上週我接受了採訪。我在算法輪迴中遇到了一個問題。我回答了這個問題，但面試官似乎並不相信。這就是爲什麼我分享相同。算法將一個輸入文件與給定數量的文件相匹配

請告訴我這個問題的任何優化方法，以便它可以幫助我在未來的訪談。

問題： -

有給出，所有文件都是ASCII文本文件20個文本文件，具有比10^9個字節少大小。還有一個輸入也給出了，這也是也是一個ASCII文件，比如input.txt。

我們的任務是將輸入文件的內容與給定的20個文件進行戰略匹配，並打印最接近的匹配文件的名稱。輸入文件的內容可能只匹配部分

在此先感謝。尋找你的迴應。

來源

2013-04-04 devsda

在這種形式下回答是不太可能的。這些文件是真實文本還是任何可打印的ASCII，或基本ASCII或擴展ASCII？結果必須是最佳匹配還是近似值？ – 2013-04-04 19:37:57

我相信有一個用於這個特定目的的系統工具。 'cmp'我相信是命名的。 POSIX兼容SO。 – yeyo 2013-04-04 19:39:23

@Kira事情告訴我，這不是面試官希望的！ – JBentley 2013-04-04 19:40:04

diff的他們並穿過WC -l，或者實現用C Levenshtein distance ++處理每一行的單個字符（或任何更合適的單元condidering受試者域）

來源

2013-04-04 19:41:48 bobah

+1，非常好的答案，但是，使用編輯距離算法有點難以實現（在我看來）。 – yeyo 2013-04-04 19:47:00

@anonymous：沒有建設性意見的倒票 - 不好 – bobah 2013-04-08 09:34:39

可以創建某種索引（示例：特里）來總結輸入文件。然後您可以檢查多少個索引匹配文檔。

例如，爲輸入文件創建一個長度爲10的樹。對於文本文件中每個長度爲10（重疊）的字符串，檢查它們在樹中的匹配數目。

來源

2013-04-04 20:24:49 ElKamina

使用trie將是低效的，因爲文件的大小很大，而使用B +樹會是更好的選擇。 – 2013-04-06 07:33:34

作爲一個建議，設計真正有能力的，可擴展的文檔相似系統，我建議閱讀第3章的Mining Massive Datasets，這是免費的在線。其中一種方法是通過將單詞計數向量化爲集合來「拼湊」數據集，然後散列這些單詞計數，並將哈希結果家族與Jaccard相似性進行比較以獲得所有文檔之間的分數。如果做得對，這可以在高精度的PB級文件上工作。可以從斯坦福大學的CS246 Slides on Locality Sensitive Hashing中讀取具有良好圖表的明確細節。書中還描述了更簡單的方法，如詞頻計數。

來源

2013-04-04 21:45:53 Pyrce

算法將一個輸入文件與給定數量的文件相匹配

回答

相關問題