高效查詢任意位置的字典的數據結構

任何人都可以提出一個適當的數據結構來容納一個字典，這將允許我查詢在特定位置有特定字母的單詞（項目）的存在嗎？例如，確定哪些詞（如果有的話）在位置x，y，z處具有字母a，b，c。插入不一定非常有效。高效查詢任意位置的字典的數據結構

這基本上是拼字遊戲問題（我也有與字母相關的分數，但這不需要關注我們）。我懷疑生物信息學家在sequence alignment的幌子下研究了同樣的問題。速度方面的最新狀態如何？

2012-12-27 Emre

對於字典中的所有單詞運行正則表達式是否不夠快？ – templatetypedef

查詢是特定類型的正則表達式，但我們尚未確定我們首先使用的字典數據結構。就是那個問題。 – Emre

基準測試只是將所有內容都放在一個動態數組中，然後用你感興趣的正則表達式爆炸一切嗎？如果這個速度足夠快，那麼做任何更復雜的事情都不值得。 – templatetypedef

如果您正在嘗試構建一個非常快速的Scrabble播放器，您可能需要查看專門爲此目的而設計的數據結構。從本質上講，GADDAG是一種壓縮的trie結構（具體而言，它是一種修改的DAWG），可以讓您向外探索並查找可以使用某組字母進行製作的所有單詞，這些字母必須受制於哪些字母必須處於什麼位置，以及找到的琴絃的總長度。

關於GADDAGs的維基百科文章更深入地介紹了關於該主題的原始論文的結構和鏈接。您可能還想將DAWG視爲出發點。

希望這會有所幫助！

來源

2012-12-27 08:41:06 templatetypedef

高效查詢任意位置的字典的數據結構

回答

相關問題