我有一个使用 FST 需要解决的问题。 基本上,我将制作一个形态解析器,此时我必须使用大型传感器。性能是这里的大问题。
最近,我在其他性能很重要的项目中使用c++工作,但现在,我正在考虑java,因为java的好处并且因为java正在变得更好。
我研究了 java 和 c++ 之间的一些比较,但我无法决定应该使用哪种语言来解决这个特定问题,因为它取决于使用的库。
我找不到关于java库的太多信息,所以,我的问题是:是否有任何性能良好的开源java库,例如我在一篇文章中读到的The RWTH FSA Toolkit,它是最快的c ++库?
谢谢大家。
对于您来说,Java 有哪些“好处”?该平台解决了您需要的什么具体问题?您必须考虑的性能限制是什么? “比较”是否公平,因为 Java 实际上极难进行基准测试。 C++ 也是如此,但你至少可以从 STL 获得一些算法边界保证。
我建议您查看 OpenFst 和 AT&T 有限状态传感器工具。还有其他的,但我认为您对 Java 的担心是本末倒置——专注于能够很好地解决您的问题。
祝你好运!
http://jautomata.sourceforge.net/和http://www.cs.duke.edu/csed/jflap/是基于Java有限状态机库,尽管我没有使用它们的经验,所以我无法评论效率。
我是 morfologik-stemming 库的开发者之一。它是纯 Java 的,无论是在构建自动机还是使用它时,它的性能都非常好。我们用它在 LanguageTool 中进行形态分析。
这里的问题是 Java 中对象的最小大小。在 C++ 中,没有虚拟方法和运行时类型识别,您的对象将精确地衡量其内容。自动机操作内存所花费的时间对性能有很大影响。
我认为这应该是选择 C++ 而不是 Java 的主要原因。
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");
}
}
}