ASP. NET MVC лучший способ поиска анаграмм в базе данных - PullRequest
Новая
       8

ASP. NET MVC лучший способ поиска анаграмм в базе данных

1 голос
/ 18 марта 2020

Я работаю над мини-проектом и пытаюсь создать программу, в которой при вводе слова он найдет анаграммы из большой базы данных (около 70000 слов), в нем также должно быть такое же количество символов, например (собаки = боги, а не боги или собаки).

До сих пор мне удавалось выполнить поиск, когда я буду искать, я найду все слова, которые содержат часть слова, которое я пишу 

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());
}

Я не уверен, что будет лучшей идеей сделать это, это довольно большой дб, и я могу себе представить, что мне нужно go несколько раз и продолжать переупорядочивать слово, чтобы проверить каждую возможность.

Это лучшее решение? или есть другой подход?

У меня есть идея, как сделать этот код, но, на мой взгляд, это не лучший подход. В случае, если это не очевидно, я очень начинающий ...

1 Ответ

1 голос
/ 18 марта 2020

Одним из простых подходов было бы сохранить каждое слово в таблице следующим образом: 

Key    | Value
---------------
dgo    | dog
dgo    | god
act    | act
act    | cat
act    | tac

Ключ - это буквы слова, упорядоченные в алфавитном порядке, тогда как значение - это фактическое слово.

Затем, чтобы найти анаграммы tac, вам просто нужно упорядочить буквы в алфавитном порядке, а затем выполнить простой поиск.

Это даст вам очень быструю производительность.

Простое Оптимизация будет иметь га sh ключ, для улучшения скорости поиска и уменьшения объема хранения данных, за счет необходимости подтверждать, что каждое слово является подлинной анаграммой (так как ха sh может привести к коллизиям, хотя это будет очень редко).

Очевидно, что если вы храните в базе данных, то сохранение ключа и значения в отдельных таблицах и объединение их вместе, вероятно, даст превосходную производительность, но для 70 тыс. слов это будет достаточно быстро для игрушечный проект, однако вы реализуете его.

РЕДАКТИРОВАТЬ

Простой пример "в памяти" этого кода будет: 

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());
}
* 1 019 * EDIT2

Чтобы построить словарь из текстового файла:

Я предполагаю, что ваш текстовый файл выглядит следующим образом: 

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);
    }
}
...