string - 一次生成一个字母的有限状态机

Question

我记得几年前上过一节课，有人给我举了一个有趣的有限状态机的例子，其中每个状态都包含一个字母，并且有多条路径指向通常跟在一个单词后面的其他字母。一些字母也有导致终止的路径，通过从有限状态机中的任何点开始并遵循有效的终止路径，可以将字母连在一起，（几乎）总是以有效的单词结束。当然，这只是语言中单词的一个子集（不幸的是，我忘记了fsm的含义）。我的问题涉及多个相关问题：
这是随机生成“伪”字的可行方法吗？我指的是一个不一定有效的词，但拼写的方式看起来是有效的。
这种技术是在任何著名的随机词生成算法中使用的，还是作为其中的一部分使用的，如果是的话，是哪种算法？
有没有其他常见的替代方法可以一次生成一个一个字母的随机单词，或者可能采用这种方式生成的随机字符串并将其强制为“伪”单词？

Answer 1

规则
正确的答案取决于“伪词”的含义，以及您希望多个生成的伪词如何相互关联。既然你已经用“过程生成”标记了这个问题，我假设你想构造一个假自然语言；所以：
每个词都应该是可发音的例如，“gotrobit”是可以接受的，但“grrhjklmpp”不是。
不同单词的总体“感觉”应该是可比的；你不希望一组芬兰语发音的单词与法语发音的单词混合在一起。
fsms的一般问题
您当然可以使用有限状态机来执行此操作，但有两个可能的陷阱：
如果fsm包含循环，则可以有非常不同的单词长度；这对需求2非常不利。如果你的FSM不包含循环，你将得到一个巨大的FSM，以便生成一个合理的词典。
在构建你的fsm时，你需要非常小心，否则你最终会得到一些不满足的词。
您可以添加一个后处理步骤，过滤掉“愚蠢”的结果，但正如我稍后将展示的，有更好的选择。
马尔可夫链
考虑到这些陷阱，一种常见的fsm播种方法是使用Markov chains。
例如，可以生成一个不确定的FSM，其中每个状态代表一个字符（或终止）；然后分析一个语料库，例如英语文本，以计算特定字符后面跟另一个字符的可能性，并使用该语料库创建转换。
使用马尔可夫链可以更容易地达到目标2；通过使用德语文本的语料库，可以得到一组完全不同的单词，它们仍然有些相似。
如前所述，陷阱依然存在。例如，看“艺术”和“训练”这两个词。这意味着“t”可以跟在“r”后面，但“r”也可以跟在“t”后面根据这些例子，你可以用“trtrtrain”这样的词结束，在我看来，这违反了1。
这可以通过让每个状态表示两个字符（而不是一个字符）的组合来减轻，但这将很快导致状态爆炸。
音节
一个更有希望的方法是不要逐字逐句地生成你的单词，而是逐字逐句地生成首先生成一个允许的音节列表，确定音节中的首选单词长度，然后选择该数量的音节。
例如，可以从使用所有辅音+元音音节的列表开始。这会给你像“德川”和“波塔罗沃”这样的词。你也可以使用一个元音+辅音音节的列表，它会给你提供像“otukag”和“opatorov”这样的单词：一种完全不同的“语言”，具有相同的简单规则。
当然，当你同时允许辅音+元音和单元音音节时，这会变得棘手。现在你可以用“tokuauga”这样的词结束，这可能是你想要的，也可能不是你想要的。
你可以更进一步，对音节类型进行分类，并添加一些简单的规则，例如：“只有两个单元音音节可以互相跟随”；或者“每个辅音元音音节后面跟着一个单元音音节，后面跟着一个辅音元音辅音音节”。现在你可以用“tokuugat”这样的词结束了。
通过选择一组允许的音节和规则，您可以得到感觉有点连贯的不同“语言”。
使用音位
如果你想写出更好的单词，你应该从使用phonemes而不是字母开始这允许您轻松地表示非ascii声音，如“ng”、“sh”和（舌头点击）。然后按照上面描述的算法执行，然后执行“音译”步骤，将音素更改为“可读”字母。
通过使用不同的音译，你可以得到更多类似语言的感觉。例如，您可以音译/sh/像'sh'（英语），或'ch'（法语）或'sch'（荷兰语）。
音位规则
Phonological rules基本上是描述上一节中规则的一种正式方式，比我前面的示例更进一步。通过选择正确的规则集，您可以创建“硬”语言、“软”语言等。例如，您可以选择将“元音+r+k+元音”更改为“元音+r+r+元音”（生成听起来像马达的语言）或更改为“元音+k+h+元音”（生成典型的矮人语言）。可能性是无穷的。
语音研究产生了很多这样的规则，帮助你创造出更多类似地球的语言。
这种方法的一个很好的例子是Drift，这是一个python程序，它使用一个音节列表和一组语音规则来生成“真实”单词。
撇开随机性和计算机生成方面不谈，我相信这或多或少是托尔金生成精灵语言和方言时所使用的方法。
结论
总结答案：
是的，使用FSM是一种可行的方法
马尔可夫链是一种流行的技术来创建这样的fsm
通过使用音节和音韵学的研究，你会得到更好的结果