我有一個從16-18長度150000左右的長度大的列表。我想從列表中搜索最近的字符串。 BKTree數據結構隨着列表變大而變慢。我想知道任何更好的數據結構，這有利於這個大型列表並提供最近的字符串搜索？替代品BKTree
途徑：我已經試過聚類串入組，建設樹簇的根條款。但是，由於我有大量的搜索查詢，速度還不夠。後綴樹不利於我用索引來搜索字符串，例如最大距離爲3左右。
UPDATE：字符串是非常相似的。字符串由具有n個滑動窗口長度的長序列生成。 所以一個字符串的後綴將是另一個字符串的前綴。
如果你有3的最大距離，那麼你就保證你的字符串至少有4個字符的相同運行。
可以由此散列長度爲4的每個段，並檢查是否每個被在數據集表示。選擇存在但內容最小的內容，然後搜索該池中的BK樹。如果你的數據集本身不是高度自我冗餘的，這應該大大減少你需要做的搜索範圍。 （一般情況下，您需要將BKTrees中的條目數量維持在之前的15倍，因此這需要一定的維護成本。）
我不確定此初始查找步驟是否便宜足以勝任後來的改進;這很大程度上取決於150k字符串的結構，以及輸入字符串是否可能與其中一個字符串匹配，或者是否有很多錯失。
另一種方法將是使用的字符串的lernmatrix-style encoding和找到最近的通過模式完成。既然你需要一個巨大的矩陣來存儲這個（可能~4M元素），我毫不猶豫地推薦這個速度。所有的矩陣乘法將花費你幾毫秒。 （你不得不在穩健萊文施泰因的方式串編碼編輯，例如通過使用相鄰的字符三角洲;這將需要工作的不可忽略的量得到工作）
當你說「最近的字符串， 「你用什麼度量來確定接近度？ –
我已經使用Levenshtein距離度量來確定接近度。 – Balaram26