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) 与第一个一样，但允许加权以便可以考虑热路径。即，如果“扭曲”一词的出现概率是“断开连接”和“处置”一词的 4 倍，则上面显示的逻辑如果结构化为:

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

注意:我知道示例集中的第 6 个字符是唯一的，因此解决示例集所需要做的就是在该字符上切换，但请假设是更长的单词列表。

此外，这不是一些家庭作业 - 我正在为 Guacamole protocol 编写解析器/拦截层.我看过二叉树、Tries、Ulam 的游戏和其他一些游戏，但没有一个符合我的要求。

Answer 1

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

当列表中有更多字符串时，一棵树会自动变得更细化，并且根据“热路径”完成对现有叶子的检查？

例如，我会在您的列表中添加类似这样的内容:

10.断开连接 7.处置 7.扭曲

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")

另一种选择当然是散列。

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