Kleenex: compiling nondeterministic transducers to deterministic streaming transducers
Kleenex: compiling nondeterministic transducers to deterministic streaming transducers
复制标题
Kleenex：将非确定性传感器编译为确定性流传感器
DOI：
10.1145/2837614.2837647
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Sebastian Paaske Tørholm
中科院分区：
文献类型：
--
作者：
Niels Bjørn Bugge Grathwohl;F. Henglein;U. Rasmussen;Kristoffer Aalund Søholm;Sebastian Paaske Tørholm
我们提出并说明Kleenex，一种语言，用于表达一般的非确定性有限换能器，其新颖的编译流串换能器基本上是最佳的流行为，最坏情况下的线性时间性能和持续的高吞吐量。它的基本理论是基于转换器分解成预言机和动作机：预言机执行输入的流贪婪消歧;动作机执行输出动作。在使用案例中，Kleenex在库存硬件上实现了约1 Gbps范围的持续高吞吐率。与GNUawk、GNUused、GNUgrep、RE 2、Ragel和正则表达式库等专业工具和相关工具相比，它表现得很好，特别是在复杂的用例中。
We present and illustrate Kleenex, a language for expressing general nondeterministic finite transducers, and its novel compilation to streaming string transducers with essentially optimal streaming behavior, worst-case linear-time performance and sustained high throughput. Its underlying theory is based on transducer decomposition into oracle and action machines: the oracle machine performs streaming greedy disambiguation of the input; the action machine performs the output actions. In use cases Kleenex achieves consistently high throughput rates around the 1 Gbps range on stock hardware. It performs well, especially in complex use cases, in comparison to both specialized and related tools such as GNUawk, GNUsed, GNUgrep, RE2, Ragel and regular-expression libraries.