c# - 前向查找算法

Question

给定格式的字符串{Length}.{Text}（例如3.foo），我想从有限列表中确定给定字符串是哪个字符串。阅读器从 0 索引开始，可以向前搜索（如果需要，可以跳过字符）。

例如，考虑以下列表：

10.disconnect
7.dispose
7.distort

确定已呈现哪些字符串的最短方法可能如下所示：

if (reader.Current == "1")
{
  // the word is "disconnect"
}
else
{
  reader.MoveForward(5);
  if (reader.Current == "p")
  {
    // the word is "dispose"
  }
  else
  {
    // the word is "distort"
  }
}

这个问题有两部分，尽管我希望有人能指出我需要阅读更多信息的正确算法或信息论方面。

1）给定一个有限的字符串列表，生成逻辑的最佳方法是平均需要最少次数的查找和比较来确定呈现的是哪个单词？

2）与第一个一样，但允许加权以便可以考虑热路径。即，如果“distort”这个词比“disconnect”和“dispose”这个词的可能性高4倍，那么上面显示的逻辑平均而言如果结构如下：

reader.MoveForward(5);
if (reader.Current == "t")
{
  // the word is distort
}
else //...

注意：我知道示例集中的第 6 个字符是唯一的，因此您需要做的就是解决示例集中的switch问题，但请假设有更长的单词列表。

此外，这不是一些家庭作业——我正在为Guacamole 协议编写解析器/拦截层。我看过 Binary Trees、Tries、Ulam's Game 和其他一些，但没有一个符合我的要求。

Answer 1

我不知道这是否有任何帮助，但无论如何我都会投入我的 5 美分。

当列表中有更多字符串时自动变得更细化的树怎么样？现有叶子的检查是针对“热路径”完成的？

例如，我会在你的列表中有这样的东西：

10.disconnect 7.dispose 7.distort

root ---- 7 "check 4th letter" ------ if "t" return "distort"
     |      "in the order of "   |
     |      "  hot paths     "    --- if "p"return "dispose"
     |
     ----10 ---- return "disconnect"

你可以动态地建立它。例如，如果您添加 7.display 它将是

root ---- 7 "check 4th letter" ------ if "t" return "distort"
     |      "in the order of "   |
     |      "  hot paths     "    --- if "p" --- "check 5th letter" --- if "o" ...
     |                                                               |
     ----10 ---- return "disconnect"                                  --- if "l" ...

因此树中的节点将有一个变量“要检查的索引”，并与可能的结果相对应（顺序是统计确定的）。所以像：

# python example
class node():
  def __init__(which_index, letter):
    self.which_index = which_index # which index this node checks to determine next node
    self.letter = letter # for which letter we go to this node
    self.leaves = SomeLinkedList()

  def add_leaf(node):
    self.leaves.putInCorrectPositionDependingOnHowHotPathItIs(node)

  def get_next(some_string):
    for leaf in self.leaves:
      if some_string[self.which_index] == leaf.letter:
         return leaf
    raise Exception("not found")

另一种选择当然是散列。

但是，如果您进行微优化，则很难说，因为还有其他因素在起作用（例如，您从内存缓存中节省的时间可能非常重要）。