用什么算法搜索词中的子词?

本文关键字：算法 搜索 什么 | 更新日期: 2023-09-27 18:17:30

我知道，也许这个问题很愚蠢，但我被困住了，我需要真正的帮助。我需要在我的项目中使用算法，可以找到所有的词是由另一个开始，并返回所有的词的尾巴。例如:查找所有以:dad

开头的单词

在字典中有:

dada, dadaism, daddled, daddling

结果:

a, aism, dled, dling

我有一个包含所有单词的字典，所以我只需要算法。有人建议我使用patricia算法，但我找不到c#的任何样本。我的字典很大，所以我需要找到一个非常快的算法。

更多信息:

  • 用什么算法搜索词中的子词?

    如何做到这一点取决于你的字典是如何排列的。如果它是一个排序的单词列表，那么您可以使用二分搜索来查找以"dad"开头的第一个单词，然后循环使用StartsWith和Substring的单词。即:

    List<string> Words = LoadWords(); // however you load them
Words.Sort();
// Now, search for "dad" (or whatever)
string prefix = "dad";
int index = Words.BinarySearch(prefix);
// If the returned index is negative, the word wasn't found.
// The index is the one's compliment of the the place where it would be in the list.
if (index < 0)
{
    index = ~index;
}
for (int i = index; i < Count && Words[i].StartsWith(prefix))
{
    Console.WriteLine(Words[i].Substring(prefix.Length));
}

    这应该很快。排序是加载后的一次性开销。你可以完全消除它如果你按排序顺序存储字典。二叉查找是O(log n)，其中n是字典中的单词数。

    如果你的字典是无序的，那么你将不得不遍历所有的单词，这将花费很多时间。

    你的字典有其他组织，这将使它占用更少的空间，这可能会更快。与创建一个排序列表相比，这些列表更复杂，需要花费更多的时间。

    这听起来像是Trie/DAWG(有向无循环词图)的完美用法。我知道帕特里夏树是一种类似尝试的变种。这里有一篇关于try和实现的好文章

    For循环对于非常小的字典来说可能相当快。但是如果你有成千上万个单词的匹配集，那就会非常慢。假设您的字典已经排序(如果没有排序)，您可以使用BinarySearch函数来定位第一个和最后一个范围项，然后使用for循环来创建您的结果。

    为了更实际，我有一个(排序的)字典，里面有354984个单词，包括这35个单词，从爸爸开始:爸爸，爸爸的，达达主义，达达主义，达达主义，达达主义，达达主义，达达主义，达达主义，达达主义，达达主义，达达主义，达达主义，达达主义，达达主义，达达主义，达达主义，达达主义，达达主义，dadap, dadas, dadburn, dadder, daddies, dadadding, daddock, daddocky, dadaddling, daddock, daddocky, dadaddums, daddy, dadynut, dade, dadenhud, daddad, ddad, ddad, ddad, ddad, ddad, ddad, ddad, ddad, ddad, ddad, ddad, ddad, ddad, ddad, ddad, ddad, ddad, ddad, ddad, dado, dado, dadodoing, dados, dadouchos, dads和daduchus。如果我遵循吉姆的方法，我将不得不执行35个"start - tswith"，这是可以的。以"sat"为前缀，我有228个单词，以"cat"为前缀，我有692个单词。对于我的字典的大小，我总共需要40个字符串比较(最坏的情况)来定位第一个和最后一个条目。

    如果你愿意使用任何tree实现，确保至少支持数字和破折号，如果你的字典包含像1st或real-time这样的记录

    我知道的最著名的是"knuth morris pratt字符串匹配算法"。

    如果你看一下链接，还有其他一些像Boyer-Moore字符串搜索算法，…这些都是通用算法，但如果你对特殊情况感兴趣，比如…在大多数情况下语言都有这种情况，例如在c#中你可以使用StartsWith, EndsWith，没有必要再实现它们。

    如果你需要一些简单的东西，你可以试试这个:

            string[] dict = new string[] { "dada", "dadaism", "daddled", "daddling" };
        string prefix = "dad";
        var words = from d in dict
                    where d.StartsWith(prefix)
                    select d.Substring(prefix.Length);

    您可以使用TRIE。你可以在这里找到一个全面的实现和教程。

    基本上，在这个结构中，你最终将从根遍历到'd'，然后到'a'，然后到'd'。你会到达一个点，你想要所有以"爸爸"开头的单词。现在把它看作根节点，你所要做的就是探索下面所有可能的路径这就是你的算法

    相关文章：