如何從字符數組中找到字符串匹配？恩。給定一個，N，T查找字符串匹配螞蟻，在字表中的棕褐色

Question

到目前爲止我的數據庫中有27個表。一個詞表（一個拼字遊戲詞表）和26個關聯表。

Table Fields 
================ 
word [id,word] 
a  [word_id,count] 
b  [word_id,count] 
... 
z  [word_id,count] 

我想弄清楚給定一個字符串匹配的單詞。

例如，如果給定的數組是a,n,t我想知道：ant, tan, at, ta, an, na。

我目前的策略是爆炸字符串中的每個字母，並找到匹配所有字母的關聯詞。

例如：

SELECT word.word 
FROM word, a, n, t 
WHERE 
    word.id = a.word_id OR 
    word.id = n.word_id OR 
    word.id = t.word_id 

但這最終打印，在他們有一個a,n or t所有單詞。

如果我將所有運算符切換爲AND，則只能匹配一個匹配項：ant。

你能幫我解決這個謎題嗎？

我還關心如何處理字符串中的重複字母。我在考慮信函關聯表中的count字段在這裏可以提供幫助。如果單詞是app，則在p關聯表中的計數將爲2。

我在正確的軌道與關聯表或有更好的方法嗎？

我試圖在php/mysql中相當有效地處理這個問題。我知道還有其他人在C，Perl，Java等之前解決了這個謎題。

Answer 1

如果你想有一個標準化的方法，這將是：

wordLetters{ 
    INT wordID, 
    CHAR[1] letter, 
    INT count, 
    PK(wordID, letter) 
} 

words{ 
    INT wordID PK, 
    VARCHAR(255) word UNIQUE 
} 

但是這種方法在性能方面的嚴重問題 - 即它需要的字表進行全表掃描。我會認爲不會有太多的字母和建議這種做法：

words{ 
    INT wordID PK, 
    VARCHAR(255) word UNIQUE, 
    INT cA KEY, 
    INT cB KEY, 
    ... 
    INT cZ KEY, 
    KEY (cE, cT, cA, cO, cI, cN), 
    ... 
} 

查找查詢將是漫長的，但它會有效地使用索引，它是由PHP代碼反正產生：

如果用戶有[a,n,t]，獲取可用的話爲：

SELECT word FROM words WHERE 
    cA <= 1 AND cB = 0 AND cC = 0 AND ... AND cY = 0 AND cZ = 0 

這個查詢（可能）使用「ETAOIN」指數不需要一個「E」話語不多存在。

此時，性能取決於可用於數據庫的索引的選擇，並且可以隨時添加更多的索引（即使在運行時）。

---

在數據庫索引：

一個普通的指數是內置在列表中選擇合適樹項目，實現高效的查找範圍（從X到Y得到的所有元素）只是排序列表。

普通索引由其排序順序定義。排序順序是：先按某一列排序，然後再按另一列排序，然後再按另一列排序...。

例如，[E,T,A,O,I,N]指數將有排序的所有的話：第一不需要的E所有的話，那麼需要一個E所有的話，那麼需要兩個E ...所有單詞。需要相同數量E s的詞將排序：首先不需要T的所有詞，然後是所有需要它的詞，然後是需要兩個T s ...的所有詞。在需要相同數量E s和T s的詞語中，那些不需要A的詞語排在第一位。

如果要求數據庫提取所有不需要E或T且最多隻有一個'X'的單詞，則可以使用此索引來滿足前兩個要求，然後檢查範圍內的所有單詞E=0, T=0。

特殊選擇ETAOIN基於短語ETAOIN SHRDLU，它以英語的頻率排列12個最常出現在英語中的字母 - 這意味着如果使用該指數，它應該過濾掉儘可能多的單詞。

您使用示例RSTLNE。當玩家沒有R s或S s時，該索引將會/可能被使用。基準查找可能會告訴您使用每個特定索引節省了多少時間。

您可以使用EXPLAIN EXTENDED查詢來查看哪些索引被考慮並隨後用於每個特定查詢以及預計將過濾多少行。例如：

EXPLAIN EXTENDED 
    SELECT word FROM words 
    WHERE cA=0 AND cB<=1 AND cC=0 AND ...