解析不规则逗号分隔值的算法

Question

假设我们有一个包含多个事物描述的列表。描述由逗号分隔的单词组成。让我们以下面的列表为例(每行是一个单独的描述):

white, leather, round
black, plastic, rectangular
wood, rectangular, brown
...

我们希望将它们解析成以下结构:(颜色、 Material 、形状)

前两个描述可以直接映射到我们的结构中。但是第三个不能。因为值的顺序不同: Material 、形状、颜色。

因此实际问题是:我们如何检测此类不规则条目并解析它们？

我想我们必须以某种方式检测每个词描述的部分。但我什至不知道从哪里开始，如何开始。我也非常感谢任何提示、算法和论文(关于相关算法)。

编辑:抱歉忘了说没有已知的固定词汇。不同类别中可能有相同的词。 但我认为我错过的最重要的事情可能是:大多数条目都是常规的。所以我想我们可以以某种方式使用它来增加字典。

Answer 1

如果没有某种约束，这是一个不可能的问题。假设您有某种字典来对单词进行分类(可能是模棱两可的)，您就可以取得一些进展。下面是算法的概要:

1. 首先，将每一行解析为三个单词，不对它们进行分类。
2. 然后使用字典为每个词分配一组候选类别(颜色、 Material 和/或形状)。
3. 如果一个词只有一个类别，则从其他两个词中删除该类别。重复直到无法取得进一步的进展。
4. 如果所有单词都属于一个类别，那么您就完成了并且找到了唯一的解决方案。
5. 如果任何词的类别为零，则这三个词不能有效组合。
6. 您现在必须猜测:选择一个具有多个类别的词，然后选择一个类别作为该词的暂定分配。重新应用第 3 步中的规则。
7. 如果任何单词有零个类别，如果没有尝试过任何类别，则返回到第 6 步；否则失败退出。
8. 如果所有单词都属于一个类别，那么您就找到了一个一致的分​​配。如果您只需要一些 解决方案，那么就用这个解决方案退出。如果您想要所有解决方案，请将此解决方案添加到一组解决方案中，然后返回到第 6 步进行另一次尝试。
9. 如果有些词仍然有多个类别，则返回第 6 步(不回溯)。