Debian Codegraph @

morfologik-fsa-builders/src/test/java/morfologik/fsa/builders/FSATraversalTest.java

raw
1 package morfologik.fsa.builders;
2
3 import static java.nio.charset.StandardCharsets.*;
4 import static morfologik.fsa.MatchResult.*;
5 import static org.junit.Assert.*;
6
7 import java.io.ByteArrayInputStream;
8 import java.io.ByteArrayOutputStream;
9 import java.io.IOException;
10 import java.nio.ByteBuffer;
11 import java.util.Arrays;
12 import java.util.HashSet;
13
14 import org.junit.Before;
15 import org.junit.Test;
16
17 import morfologik.fsa.FSA;
18 import morfologik.fsa.FSA5;
19 import morfologik.fsa.FSATraversal;
20 import morfologik.fsa.MatchResult;
21
22 /**
23 * Tests {@link FSATraversal}.
24 */
25 public final class FSATraversalTest extends TestBase {
26 private FSA fsa;
27
28 @Before
29 public void setUp() throws Exception {
30 fsa = FSA.read(this.getClass().getResourceAsStream("en_tst.dict"));
31 }
32
33 @Test
34 public void testAutomatonHasPrefixBug() throws Exception {
35 FSA fsa = FSABuilder.build(Arrays.asList(
36 "a".getBytes(UTF_8),
37 "ab".getBytes(UTF_8),
38 "abc".getBytes(UTF_8),
39 "ad".getBytes(UTF_8),
40 "bcd".getBytes(UTF_8),
41 "bce".getBytes(UTF_8)));
42
43 FSATraversal fsaTraversal = new FSATraversal(fsa);
44 assertEquals(EXACT_MATCH, fsaTraversal.match("a".getBytes(UTF_8)).kind);
45 assertEquals(EXACT_MATCH, fsaTraversal.match("ab".getBytes(UTF_8)).kind);
46 assertEquals(EXACT_MATCH, fsaTraversal.match("abc".getBytes(UTF_8)).kind);
47 assertEquals(EXACT_MATCH, fsaTraversal.match("ad".getBytes(UTF_8)).kind);
48
49 assertEquals(SEQUENCE_IS_A_PREFIX, fsaTraversal.match("b".getBytes(UTF_8)).kind);
50 assertEquals(SEQUENCE_IS_A_PREFIX, fsaTraversal.match("bc".getBytes(UTF_8)).kind);
51
52 MatchResult m;
53
54 m = fsaTraversal.match("abcd".getBytes(UTF_8));
55 assertEquals(AUTOMATON_HAS_PREFIX, m.kind);
56 assertEquals(3, m.index);
57
58 m = fsaTraversal.match("ade".getBytes(UTF_8));
59 assertEquals(AUTOMATON_HAS_PREFIX, m.kind);
60 assertEquals(2, m.index);
61
62 m = fsaTraversal.match("ax".getBytes(UTF_8));
63 assertEquals(AUTOMATON_HAS_PREFIX, m.kind);
64 assertEquals(1, m.index);
65
66 assertEquals(NO_MATCH, fsaTraversal.match("d".getBytes(UTF_8)).kind);
67 }
68
69 @Test
70 public void testTraversalWithIterable() {
71 int count = 0;
72 for (ByteBuffer bb : fsa.getSequences()) {
73 assertEquals(0, bb.arrayOffset());
74 assertEquals(0, bb.position());
75 count++;
76 }
77 assertEquals(346773, count);
78 }
79
80 @Test
81 public void testPerfectHash() throws IOException {
82 byte[][] input = new byte[][] {
83 { 'a' },
84 { 'a', 'b', 'a' },
85 { 'a', 'c' },
86 { 'b' },
87 { 'b', 'a' },
88 { 'c' }, };
89
90 Arrays.sort(input, FSABuilder.LEXICAL_ORDERING);
91 FSA s = FSABuilder.build(input);
92
93 final byte[] fsaData =
94 new FSA5Serializer().withNumbers()
95 .serialize(s, new ByteArrayOutputStream())
96 .toByteArray();
97
98 final FSA5 fsa = FSA.read(new ByteArrayInputStream(fsaData), FSA5.class);
99 final FSATraversal traversal = new FSATraversal(fsa);
100
101 int i = 0;
102 for (byte[] seq : input) {
103 assertEquals(new String(seq), i++, traversal.perfectHash(seq));
104 }
105
106 // Check if the total number of sequences is encoded at the root node.
107 assertEquals(6, fsa.getRightLanguageCount(fsa.getRootNode()));
108
109 // Check sub/super sequence scenarios.
110 assertEquals(AUTOMATON_HAS_PREFIX, traversal.perfectHash("abax".getBytes(UTF_8)));
111 assertEquals(AUTOMATON_HAS_PREFIX, traversal.perfectHash("abx".getBytes(UTF_8)));
112 assertEquals(SEQUENCE_IS_A_PREFIX, traversal.perfectHash("ab".getBytes(UTF_8)));
113 assertEquals(NO_MATCH, traversal.perfectHash("d".getBytes(UTF_8)));
114 assertEquals(NO_MATCH, traversal.perfectHash(new byte[] { 0 }));
115
116 assertTrue(AUTOMATON_HAS_PREFIX < 0);
117 assertTrue(SEQUENCE_IS_A_PREFIX < 0);
118 assertTrue(NO_MATCH < 0);
119 }
120
121 /**
122 *
123 */
124 @Test
125 public void testRecursiveTraversal() {
126 final int[] counter = new int[] { 0 };
127
128 class Recursion {
129 public void dumpNode(final int node) {
130 int arc = fsa.getFirstArc(node);
131 do {
132 if (fsa.isArcFinal(arc)) {
133 counter[0]++;
134 }
135
136 if (!fsa.isArcTerminal(arc)) {
137 dumpNode(fsa.getEndNode(arc));
138 }
139
140 arc = fsa.getNextArc(arc);
141 } while (arc != 0);
142 }
143 }
144
145 new Recursion().dumpNode(fsa.getRootNode());
146
147 assertEquals(346773, counter[0]);
148 }
149
150 @Test
151 public void testMatch() throws IOException {
152 final FSA fsa = FSA.read(this.getClass().getResourceAsStream("abc.fsa"));
153 final FSATraversal traversalHelper = new FSATraversal(fsa);
154
155 MatchResult m = traversalHelper.match("ax".getBytes());
156 assertEquals(AUTOMATON_HAS_PREFIX, m.kind);
157 assertEquals(1, m.index);
158 assertEquals(new HashSet<String>(Arrays.asList("ba", "c")), suffixes(fsa, m.node));
159
160 assertEquals(EXACT_MATCH, traversalHelper.match("aba".getBytes()).kind);
161
162 m = traversalHelper.match("abalonger".getBytes());
163 assertEquals(AUTOMATON_HAS_PREFIX, m.kind);
164 assertEquals("longer", "abalonger".substring(m.index));
165
166 m = traversalHelper.match("ab".getBytes());
167 assertEquals(SEQUENCE_IS_A_PREFIX, m.kind);
168 assertEquals(new HashSet<String>(Arrays.asList("a")), suffixes(fsa, m.node));
169 }
170
171 /**
172 * Return all sequences reachable from a given node, as strings.
173 */
174 private HashSet<String> suffixes(FSA fsa, int node) {
175 HashSet<String> result = new HashSet<String>();
176 for (ByteBuffer bb : fsa.getSequences(node)) {
177 result.add(new String(bb.array(), bb.position(), bb.remaining(), UTF_8));
178 }
179 return result;
180 }
181 }