c# - ASP.NET MVC 在数据库中搜索字谜的最佳方法
问题描述
我正在做一个迷你项目并尝试制作一个程序,当您输入一个单词时,它会从大约 70000 个单词的大数据库中找到字谜,它还需要具有相同数量的字符,例如(dogs = gods 和不是上帝或狗)。
到目前为止,我设法进行了搜索,当我搜索时,我会找到所有包含我写的单词的一部分的单词
public ActionResult CheckAnagram(string word)
{
IQueryable<Anagram> wordDictionary = db.Anagrams;
if (!String.IsNullOrEmpty(word))
{
wordDictionary = wordDictionary.Where(a => a.Name.Contains(word));
}
return View(wordDictionary.ToList());
}
我不确定这样做的最佳主意是什么,这是一个相当大的数据库,我可以想象的是我必须多次去并不断重新排序单词以检查每种可能性。
这是最好的解决方案吗?还是有另一种方法?
我知道如何制作这段代码,但在我看来这似乎不是最好的方法。如果不是很明显,我是个初学者...
解决方案
一种简单的方法是将每个单词存储在这样的表中:
Key | Value
---------------
dgo | dog
dgo | god
act | act
act | cat
act | tac
键是按字母顺序排列的单词的字母,而值是实际单词。
然后,要找到tac
您的字谜,只需按字母顺序排列字母,然后执行简单的查找。
这将使您获得非常快的性能。
一个简单的优化是散列密钥,以提高查找速度并减少数据存储,代价是必须确认每个单词都是真正的字谜(因为散列可能导致冲突,尽管这种情况非常罕见)。
显然,如果您将存储在数据库中,那么将键和值存储在单独的表中并将它们连接在一起可能会提供出色的性能,但是对于 70k 单词,无论您如何实现它,对于一个玩具项目来说它都足够快。
编辑
此代码的一个简单的“内存中”示例是:
void Main()
{
// Setup a database of anagrams. We are using a simple
// dictionary here.
var words = new Dictionary<string, IEnumerable<string>>
{
["dgo"] = new List<string> { "dog", "god"},
["act"] = new List<string> { "act", "cat", "tac" }
};
// Ask the user for a word to search.
var wordToSearch = Console.ReadLine();
// Get the lookup key.
var key = GetKey(wordToSearch);
// Lookup the anagrams, excluding the word that was input.
var anagrams = words[key].Where(word => word != wordToSearch);
// Print out the anagrams.
foreach(var anagram in anagrams)
{
Console.WriteLine(anagram);
}
}
// Calculates a key for "word". This function must return a value that
// will be the same for any anagram of "word".
public string GetKey(string word)
{
return new String(word.OrderBy(c => c).ToArray());
}
编辑2
从文本文件构造字典:
我假设您的文本文件如下所示:
cat
dog
tac
act
god
然后下面的代码可以读进去:
var file = @"C:\temp\words.txt";
var words = new Dictionary<string, IList<string>>();
using (var stream = File.OpenRead(file))
using (var reader = new StreamReader(stream))
{
while(!reader.EndOfStream)
{
var word = reader.ReadLine().Trim();
var key2 = GetKey(word);
if (!words.ContainsKey(key2))
{
words[key2] = new List<string>();
}
words[key2].Add(word);
}
}