algorithm - 分词最有效的算法？

Question

我一直在寻找一种高效的单词划分算法，但没有取得多大成功。例如，给定单词 hello 我想获取该单词的所有可能分区:{h,e,l,l,o},{h,e,l,lo},{h,e,llo},。 ..，{你好}。我发现的所有内容都在谈论分词，这不是我的意思。

提前致谢!

Answer 1

您展示了一些示例，我们可以在这些示例中专注于逗号。 要么有逗号，要么没有。

 Word        Commas
{h,e,l,l,o}  1111
{h,e,l,l o}  1110
{h,e,l l o}  1100
...
{h e l l o}  0000

所以很明显，在 4 个位置上，可能有或没有逗号，彼此独立。您需要 4 位来对分区进行编码，这是 2^4 种可能性，我猜是 16。

所以你可以形成一个循环:

for (int i = 0; i < 15; ++i)
    bitsplit ("hello", i);

并在遍历 i 的二进制表示的位的同时遍历你的单词。例如，对于 11，您设置了位:8+2+1 = 1011。这意味着 {h,el,l,o}。