还有一个关于TST的问题 [英] One more question on TSTs

问题描述

我几乎了解TST，我只需要知道答案

到此：

制作TST（用C ++）时会有它的叶子节点单词使得语言和每个单元的分类标识符，每个图层的每个图层将表示搜索中另一个字母的比较

string，当一个特定节点本身是一个叶子节点时会发生什么，但是

也有它自己的叶子节点？即具体而言，就代码而言，

适用于此特定情况。


例如，节点sp_he具有叶节点sp_hel （可能还有其他人）

但是sp_help是叶节点，如sp_help，是一个SQL单词，但它也有自己的叶子节点，sp_helpindex和sp_helpindex。例如。

我想在C ++代码中用什么来确定这是什么时候这是什么？

解决方案

Bonj写道：

我几乎了解TST，我只需要知道答案：搜索字符串中的更多字母，当某个特定节点本身是叶子节点时会发生什么，还有它自己的叶子节点？具体而言，就代码而言，对于这个特定的场景。例如，节点sp_he等。具有叶节点sp_hel （可能还有其他人）但是sp_help是叶节点，如sp_help，是一个SQL单词，但它还有自己的叶节点，sp_helpindex和例如。
我想在C ++代码中用什么来识别
这是什么情况？

你'' d在每个节点的数据中存储一些内容，将其标识为合法的终端节点。例如，将关键字分类器值存储在所有潜在的
端节点中，将-1存储在所有其他端节点中。当然，所有叶节点都是端节点。


如果树中的数据是动态分配的（我不认为它会是b / b
在你的情况下），那么你可以简单地为非终端节点存储空。


-cd


PS：我很高兴你坚持下去了！我打算在这里发布一个小的TST

演示版，但是没有时间。

>您将在每个节点的数据中存储一些内容，将其标识为合法的

end-node。例如，将关键字分类器值存储在所有可能的终端节点中，将-1存储在所有其他节点中。当然，所有叶节点都是端节点。


对，得到那个位。我仍然有点浑浊的是如何决定

是否''传入''（即in-parameter）字符串'找到它的方式

通过树应*使用*此结束节点（如果存在），或进行另一次

比较。例如，如果sp_helpindex，是''传入''字符串，然后

它想要到达的节点（其目标）是sp_helpindex。节点。它将通过sp_help进入
。节点，但将以某种方式必须选择进行另一次比较，并沿着路径向sp_helpindex，/ b $ b的节点走，而不是停在sp_help。 。

此外，sp_help也必须通过sp_help进行节点，但是

必须停在那里。

" sp_helpgobbledegook"将不得不经过sp_help还有，但是必须

决定与''g''字符进行另一次比较，然后

掉出来。

我目前的想法是传入字符串的长度以及

（无论如何都会在调用算法中知道）并使其成为每个

节点知道如何一根弦必须要停在它上面。我很确定这会是什么工作，虽然我还没有编写算法，但是我希望有一个明确的算法来解决这个问题。在我编写它之前，当我编程速度最快时编程最好

！

如果树中的数据是动态分配的（我不会想到）它会在你的情况下），然后你可以简单地为非端节点存储null。


这是我真正想知道的另一点。我怎样才能构建一个包含这样的单词节点的算法

，但是*不是*动态生成的？

只有这样，我才能想到我现在要做的是，如果我有一个

''节点''类（或结构）。这意味着在运行时填充它。这意味着

在程序启动时加载数据。还有另一种方式吗？

-cd

PS：我很高兴你坚持下去！


干杯！当你这样做时，我总觉得它是最好的。唯一让我失望的事情是这将是无用的，我永远不会被它永远不会工作推迟。 - 因为如果

任何人都可以让它工作，我就没有理由不能。这是我实际上*想要*作为我日常生活中使用的产品的一些东西

工作，所以它不可能毫无意义。否则，如果我看不到自己

使用它，我就不可能有动力去开始它！我认为最优秀的节目是你自己指定的节目和

为自己写的......

BTW欢呼帮助顺便说一句，我认为我终于掌握了（虽然我不应该说得太快......）


我我打算在这里发布一个小的TST
演示版，但是还没有时间。


让我知道你是否/当你做...


干杯

" Bonj" <博** @ discussions.microsoft.com>在消息中写道

news：85 ********************************** @ microsof t.com

您将在每个节点的数据中存储一些内容，将其标识为合法的终端节点。例如，将关键字分类器值存储在所有可能的终端节点中，将-1存储在所有其他终端节点中。当然，所有的叶节点都是端节点。

对，得到那个位。我仍然有点浑浊的是如何决定是否'通过树'找到它的''传入''（即in-parameter）字符串应该*使用*此终端节点（如果存在），或
进行另一次比较。例如，如果sp_helpindex，是
''传入''字符串，然后它想要到达的节点（其目标）
是sp_helpindex节点。它将通过sp_help进行。节点，但
将以某种方式选择进行另一次比较，然后沿着sp_helpindex指向节点的路线，而不是停在
sp_help。

如果下一个字符是空格或文本结尾，则停在sp_help。

否则，sp_help不可能匹配，所以你继续。

-

祝你好运，

Igor Tandetnik


" ;有两次，我被[国会议员]问过，''祈祷，

巴贝奇先生，如果你把错误的数字投入到机器中，那将是正确的

答案出来了吗？''我无法正确地理解那些可能引发这样一个问题的想法混淆。 - 查尔斯

Babbage

I almost understand TSTs, to the point where I just need to know the answer
to this:
When making a TST (in C++) that will have as its leaf nodes words that make
up SQL language and an categorising identifier for each one, and each layer
of the tree will represent comparison of a further letter within the search
string, what will happen when a particular node is a leaf node itself, but
also has leaf nodes of its own? i.e. specifically, as far as the code goes,
for this particular scenario.

for instance, the node "sp_he" has leaf nodes "sp_hel" (and possibly others)
but "sp_help" is a leaf nodes, as "sp_help" is a SQL word, BUT it also has
leaf nodes of its own, "sp_helpindex" for example.
What would I want to have going on in the C++ code to identify when this is
the case?

解决方案

Bonj wrote:

I almost understand TSTs, to the point where I just need to know the
answer to this:
When making a TST (in C++) that will have as its leaf nodes words
that make up SQL language and an categorising identifier for each
one, and each layer of the tree will represent comparison of a
further letter within the search string, what will happen when a
particular node is a leaf node itself, but also has leaf nodes of its
own? i.e. specifically, as far as the code goes, for this particular
scenario.

for instance, the node "sp_he" has leaf nodes "sp_hel" (and possibly
others) but "sp_help" is a leaf nodes, as "sp_help" is a SQL word,
BUT it also has leaf nodes of its own, "sp_helpindex" for example.
What would I want to have going on in the C++ code to identify when
this is the case?

You''d store something in the data of each node that identifies it as a legal
end-node. For example, store your keyword classifier value in all potential
end-nodes, and -1 in all others. Of course, all leaf nodes are end-nodes.

If the data in your tree is dynamically allocated (I wouldn''t think it would
be in your case), then you could simply store null for non-end nodes.

-cd

PS: I''m glad you stuck with it! I was going to put together a small TST
demo to post here, but just haven''t had the time.

> You''d store something in the data of each node that identifies it as a legal

end-node. For example, store your keyword classifier value in all potential
end-nodes, and -1 in all others. Of course, all leaf nodes are end-nodes.
Right, got that bit. The bit I''m still a bit muddy on is how to decide
whether the ''incoming'' (i.e. in-parameter) string that''s finding its way
through the tree should *use* this end-node (if it exists), or make another
comparison. For instance, if "sp_helpindex" was the ''incoming'' string, then
the node that it wants to get to (its target) is the "sp_helpindex" node. It
will go via the "sp_help" node, but will somehow have to choose to make
another comparison and go down the route towards the node for "sp_helpindex",
rather than stop at "sp_help".
Further, "sp_help" will also have to go via the "sp_help" node, but will
have to stop there.
"sp_helpgobbledegook" will have to go via "sp_help" aswell, but will have to
take the decision to make another comparison with its ''g'' character, and then
fall out.
My current thinking is to also pass in the length of the string aswell
(which will be known in the calling algorithm anyway) and make it so each
node knows how long a string must be to stop at it. I''m pretty sure this will
work, although I haven''t got the algorithm written yet, I like to have a
clear path for the alrogithm worked out before I write it, as I program best
when I program fast!


If the data in your tree is dynamically allocated (I wouldn''t think it would
be in your case), then you could simply store null for non-end nodes.
That''s the other bit I really want to know. How can I construct an algorithm
that contains word nodes like this, but *isn''t* dynamically generated? The
only way I can think how I''m going to do it at the moment is if I have a
''node'' class (or struct). Which means populating it at runtime. Which means
loading the data when the program starts. Is there another way?

-cd

PS: I''m glad you stuck with it!
Cheers! I always find it''s best when you do. The only thing that puts me off
is "this''ll be useless", I''m never put off by "it''ll never work" - because if
anybody can get it to work, there''s no reason why I can''t. And this is
something that I actually *want* as a product to use in my own day to day
work, so it can''t possibly be pointless. Otherwise, if I can''t see myself
using it, I couldn''t possibly have the motivation to have even started it! I
think the best programs are the ones that you actually specify yourself and
write for yourself...
BTW cheers for the help on the RICHEDIT by the way, I think I''ve finally
mastered that (although I shouldn''t speak too soon...)

I was going to put together a small TST
demo to post here, but just haven''t had the time.
Let me know if/ when you do...

Cheers

"Bonj" <Bo**@discussions.microsoft.com> wrote in message
news:85**********************************@microsof t.com

You''d store something in the data of each node that identifies it as
a legal end-node. For example, store your keyword classifier value
in all potential end-nodes, and -1 in all others. Of course, all
leaf nodes are end-nodes.

Right, got that bit. The bit I''m still a bit muddy on is how to decide
whether the ''incoming'' (i.e. in-parameter) string that''s finding its
way through the tree should *use* this end-node (if it exists), or
make another comparison. For instance, if "sp_helpindex" was the
''incoming'' string, then the node that it wants to get to (its target)
is the "sp_helpindex" node. It will go via the "sp_help" node, but
will somehow have to choose to make another comparison and go down
the route towards the node for "sp_helpindex", rather than stop at
"sp_help".

If the next character is whitespace or end-of-text, you stop at sp_help.
Otherwise, it sp_help can''t possibly match, so you continue on.
--
With best wishes,
Igor Tandetnik

"On two occasions, I have been asked [by members of Parliament], ''Pray,
Mr. Babbage, if you put into the machine wrong figures, will the right
answers come out?'' I am not able to rightly apprehend the kind of
confusion of ideas that could provoke such a question." -- Charles
Babbage

这篇关于还有一个关于TST的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！