| 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 |
} |