9

我有一个问题需要使用 FST 来解决。基本上，我将制作一个形态解析器，此时我必须使用大型传感器。性能是这里的大问题。

最近，我在其他对性能很重要的项目中使用 c++ 工作，但现在，我正在考虑使用 java，因为 java 的好处并且因为 java 越来越好。

我研究了 java 和 c++ 之间的一些比较，但我无法决定应该使用哪种语言来解决这个特定问题，因为它取决于使用的 lib。

我找不到关于 java 库的太多信息，所以，我的问题是：是否有任何性能良好的开源 java 库，比如我在一篇文章中读到的最快的 c++ 库中的 RWTH FSA 工具包？

谢谢大家。

4

6 回答 6

4

对您而言，Java 的“好处”是什么？该平台解决了您需要的哪些具体问题？您必须考虑的性能限制是什么？“比较”是否公平，因为 Java 实际上极难进行基准测试。C++ 也是如此，但您至少可以从 STL 获得一些算法边界保证。

我建议您查看 OpenFst 和 AT&T 有限状态转换器工具。还有其他的，但我认为你对 Java 的担心是本末倒置——专注于什么能很好地解决你的问题。

祝你好运！

于 2011-02-01T20:53:14.310 回答
2

http://jautomata.sourceforge.net/和http://www.cs.duke.edu/csed/jflap/是基于 Java 有限状态机库的，虽然我没有使用它们的经验，所以我无法评论效率。

于 2011-08-11T05:32:47.083 回答
2

我是morfologik-stemming库的开发人员之一。它是纯 Java，无论是在构建自动机时还是在使用时，它的性能都非常好。我们用它在 LanguageTool 中进行形态分析。

于 2012-06-19T08:21:40.570 回答
0

OpenFST 是一个非常全面的 C++ 有限状态转换器框架。CMU 的一些人将其移植到 Java 中，用于他们的自然语言处理。

描述它的博客文章系列。
该代码位于svn 上。

更新：我在这里将它移植到 java

于 2014-10-14T04:11:30.767 回答
0

这里的问题是 Java 中对象的最小大小。在 C++ 中，如果没有虚拟方法和运行时类型识别，您的对象会准确地衡量它们的内容。自动机操作内存所花费的时间对性能有很大影响。

我认为这应该是选择 C++ 而不是 Java 的主要原因。

于 2012-02-05T17:52:58.090 回答
0

Lucene 有一个优秀的 FST实现，它易于使用和高性能，使得 Elasticsearch、Solr 等查询引擎能够提供非常快速的亚秒级基于术语的查询。我举个例子：

import com.google.common.base.Preconditions;
import org.apache.lucene.store.ByteArrayDataInput;
import org.apache.lucene.store.DataInput;
import org.apache.lucene.store.GrowableByteArrayDataOutput;
import org.apache.lucene.util.BytesRef;
import org.apache.lucene.util.IntsRefBuilder;
import org.apache.lucene.util.fst.Builder;
import org.apache.lucene.util.fst.FST;
import org.apache.lucene.util.fst.PositiveIntOutputs;
import org.apache.lucene.util.fst.Util;

import java.io.IOException;

public class T {

    private final String inputValues[] = {"cat", "dog", "dogs"};
    private final long outputValues[] = {5, 7, 12};

    // https://lucene.apache.org/core/8_4_0/core/org/apache/lucene/util/fst/package-summary.html
    public static void main(String[] args) throws IOException {

        T t = new T();

        FST<Long> fst = t.buildFSTInMemory();
        System.out.println(String.format("memory used for fst is %d bytes", fst.ramBytesUsed()));
        t.searchFST(fst);
        byte[] bytes = t.serialize(fst);
        System.out.println(String.format("length of serialized fst is %d bytes", bytes.length));
        fst = t.deserialize(bytes);
        t.searchFST(fst);
    }

    private FST<Long> buildFSTInMemory() throws IOException {
        // Input values (keys). These must be provided to Builder in Unicode sorted order! Use Collections.sort() to sort inputValues first.

        PositiveIntOutputs outputs = PositiveIntOutputs.getSingleton();
        Builder<Long> builder = new Builder<Long>(FST.INPUT_TYPE.BYTE1, outputs);
        BytesRef scratchBytes = new BytesRef();
        IntsRefBuilder scratchInts = new IntsRefBuilder();
        for (int i = 0; i < inputValues.length; i++) {
//            scratchBytes.copyChars(inputValues[i]);
            scratchBytes.bytes = inputValues[i].getBytes();
            scratchBytes.offset = 0;
            scratchBytes.length = inputValues[i].length();
            builder.add(Util.toIntsRef(scratchBytes, scratchInts), outputValues[i]);
        }
        FST<Long> fst = builder.finish();

        return fst;
    }

    private FST<Long> deserialize(byte[] bytes) throws IOException {
        DataInput in = new ByteArrayDataInput(bytes);
        PositiveIntOutputs outputs = PositiveIntOutputs.getSingleton();
        FST<Long> fst = new FST<Long>(in, outputs);
        return fst;
    }

    private byte[] serialize(FST<Long> fst) throws IOException {
        final int capicity = 32;
        GrowableByteArrayDataOutput out = new GrowableByteArrayDataOutput(capicity);
        fst.save(out);

        return out.getBytes();
    }

    private void searchFST(FST<Long> fst) throws IOException {
        for (int i = 0; i < inputValues.length; i++) {
            Long value = Util.get(fst, new BytesRef(inputValues[i]));
            Preconditions.checkState(value == outputValues[i], "fatal error");
        }
    }
}
于 2021-07-18T03:09:38.940 回答