| 1 |
package morfologik.fsa.builders; |
| 2 |
|
| 3 |
import java.io.IOException; |
| 4 |
import java.io.StringWriter; |
| 5 |
import java.io.Writer; |
| 6 |
import java.util.BitSet; |
| 7 |
import java.util.TreeMap; |
| 8 |
|
| 9 |
import morfologik.fsa.FSA; |
| 10 |
import morfologik.fsa.FSA5; |
| 11 |
import morfologik.fsa.FSAFlags; |
| 12 |
import morfologik.fsa.StateVisitor; |
| 13 |
|
| 14 |
import com.carrotsearch.hppc.IntIntHashMap; |
| 15 |
|
| 16 |
/** |
| 17 |
* Other FSA-related utilities not directly associated with the class hierarchy. |
| 18 |
*/ |
| 19 |
public final class FSAUtils { |
| 20 |
public final static class IntIntHolder { |
| 21 |
public int a; |
| 22 |
public int b; |
| 23 |
|
| 24 |
public IntIntHolder(int a, int b) { |
| 25 |
this.a = a; |
| 26 |
this.b = b; |
| 27 |
} |
| 28 |
|
| 29 |
public IntIntHolder() { |
| 30 |
} |
| 31 |
} |
| 32 |
|
| 33 |
/** |
| 34 |
* Returns the right-language reachable from a given FSA node, formatted as an |
| 35 |
* input for the graphviz package (expressed in the <code>dot</code> |
| 36 |
* language). |
| 37 |
* |
| 38 |
* @param fsa The automaton to visualize. |
| 39 |
* @param node Starting node (subgraph will be visualized unless it's the automaton's root node). |
| 40 |
* @return Returns the dot language description of the automaton. |
| 41 |
*/ |
| 42 |
public static String toDot(FSA fsa, int node) { |
| 43 |
try { |
| 44 |
StringWriter w = new StringWriter(); |
| 45 |
toDot(w, fsa, node); |
| 46 |
return w.toString(); |
| 47 |
} catch (IOException e) { |
| 48 |
throw new RuntimeException(e); |
| 49 |
} |
| 50 |
} |
| 51 |
|
| 52 |
/** |
| 53 |
* Saves the right-language reachable from a given FSA node, formatted as an |
| 54 |
* input for the graphviz package (expressed in the <code>dot</code> |
| 55 |
* language), to the given writer. |
| 56 |
* |
| 57 |
* @param w The writer to write dot language description of the automaton. |
| 58 |
* @param fsa The automaton to visualize. |
| 59 |
* @param node Starting node (subgraph will be visualized unless it's the automaton's root node). |
| 60 |
* @throws IOException Rethrown if an I/O exception occurs. |
| 61 |
*/ |
| 62 |
public static void toDot(Writer w, FSA fsa, int node) throws IOException { |
| 63 |
w.write("digraph Automaton {\n"); |
| 64 |
w.write(" rankdir = LR;\n"); |
| 65 |
|
| 66 |
final BitSet visited = new BitSet(); |
| 67 |
|
| 68 |
w.write(" stop [shape=doublecircle,label=\"\"];\n"); |
| 69 |
w.write(" initial [shape=plaintext,label=\"\"];\n"); |
| 70 |
w.write(" initial -> " + node + "\n\n"); |
| 71 |
|
| 72 |
visitNode(w, 0, fsa, node, visited); |
| 73 |
w.write("}\n"); |
| 74 |
} |
| 75 |
|
| 76 |
private static void visitNode(Writer w, int d, FSA fsa, int s, BitSet visited) throws IOException { |
| 77 |
visited.set(s); |
| 78 |
w.write(" "); |
| 79 |
w.write(Integer.toString(s)); |
| 80 |
|
| 81 |
if (fsa.getFlags().contains(FSAFlags.NUMBERS)) { |
| 82 |
int nodeNumber = fsa.getRightLanguageCount(s); |
| 83 |
w.write(" [shape=circle,label=\"" + nodeNumber + "\"];\n"); |
| 84 |
} else { |
| 85 |
w.write(" [shape=circle,label=\"\"];\n"); |
| 86 |
} |
| 87 |
|
| 88 |
for (int arc = fsa.getFirstArc(s); arc != 0; arc = fsa.getNextArc(arc)) { |
| 89 |
w.write(" "); |
| 90 |
w.write(Integer.toString(s)); |
| 91 |
w.write(" -> "); |
| 92 |
if (fsa.isArcTerminal(arc)) { |
| 93 |
w.write("stop"); |
| 94 |
} else { |
| 95 |
w.write(Integer.toString(fsa.getEndNode(arc))); |
| 96 |
} |
| 97 |
|
| 98 |
final byte label = fsa.getArcLabel(arc); |
| 99 |
w.write(" [label=\""); |
| 100 |
if (Character.isLetterOrDigit(label)) |
| 101 |
w.write((char) label); |
| 102 |
else { |
| 103 |
w.write("0x"); |
| 104 |
w.write(Integer.toHexString(label & 0xFF)); |
| 105 |
} |
| 106 |
w.write("\""); |
| 107 |
if (fsa.isArcFinal(arc)) |
| 108 |
w.write(" arrowhead=\"tee\""); |
| 109 |
if (fsa instanceof FSA5) { |
| 110 |
if (((FSA5) fsa).isNextSet(arc)) { |
| 111 |
w.write(" color=\"blue\""); |
| 112 |
} |
| 113 |
} |
| 114 |
|
| 115 |
w.write("]\n"); |
| 116 |
} |
| 117 |
|
| 118 |
for (int arc = fsa.getFirstArc(s); arc != 0; arc = fsa.getNextArc(arc)) { |
| 119 |
if (!fsa.isArcTerminal(arc)) { |
| 120 |
int endNode = fsa.getEndNode(arc); |
| 121 |
if (!visited.get(endNode)) { |
| 122 |
visitNode(w, d + 1, fsa, endNode, visited); |
| 123 |
} |
| 124 |
} |
| 125 |
} |
| 126 |
} |
| 127 |
|
| 128 |
/** |
| 129 |
* Calculate fan-out ratio (how many nodes have a given number of outgoing arcs). |
| 130 |
* |
| 131 |
* @param fsa The automaton to calculate fanout for. |
| 132 |
* @param root The starting node for calculations. |
| 133 |
* |
| 134 |
* @return The returned map contains keys for the number of outgoing arcs and |
| 135 |
* an associated value being the number of nodes with that arc number. |
| 136 |
*/ |
| 137 |
public static TreeMap<Integer, Integer> calculateFanOuts(final FSA fsa, int root) { |
| 138 |
final int[] result = new int[256]; |
| 139 |
fsa.visitInPreOrder(new StateVisitor() { |
| 140 |
public boolean accept(int state) { |
| 141 |
int count = 0; |
| 142 |
for (int arc = fsa.getFirstArc(state); arc != 0; arc = fsa.getNextArc(arc)) { |
| 143 |
count++; |
| 144 |
} |
| 145 |
result[count]++; |
| 146 |
return true; |
| 147 |
} |
| 148 |
}); |
| 149 |
|
| 150 |
TreeMap<Integer, Integer> output = new TreeMap<Integer, Integer>(); |
| 151 |
|
| 152 |
int low = 1; // Omit #0, there is always a single node like that (dummy). |
| 153 |
while (low < result.length && result[low] == 0) { |
| 154 |
low++; |
| 155 |
} |
| 156 |
|
| 157 |
int high = result.length - 1; |
| 158 |
while (high >= 0 && result[high] == 0) { |
| 159 |
high--; |
| 160 |
} |
| 161 |
|
| 162 |
for (int i = low; i <= high; i++) { |
| 163 |
output.put(i, result[i]); |
| 164 |
} |
| 165 |
|
| 166 |
return output; |
| 167 |
} |
| 168 |
|
| 169 |
/** |
| 170 |
* Calculate the size of "right language" for each state in an FSA. The right |
| 171 |
* language is the number of sequences encoded from a given node in the automaton. |
| 172 |
* |
| 173 |
* @param fsa The automaton to calculate right language for. |
| 174 |
* @return Returns a map with node identifiers as keys and their right language |
| 175 |
* counts as associated values. |
| 176 |
*/ |
| 177 |
public static IntIntHashMap rightLanguageForAllStates(final FSA fsa) { |
| 178 |
final IntIntHashMap numbers = new IntIntHashMap(); |
| 179 |
|
| 180 |
fsa.visitInPostOrder(new StateVisitor() { |
| 181 |
public boolean accept(int state) { |
| 182 |
int thisNodeNumber = 0; |
| 183 |
for (int arc = fsa.getFirstArc(state); arc != 0; arc = fsa.getNextArc(arc)) { |
| 184 |
thisNodeNumber += (fsa.isArcFinal(arc) ? 1 : 0) |
| 185 |
+ (fsa.isArcTerminal(arc) ? 0 : numbers.get(fsa.getEndNode(arc))); |
| 186 |
} |
| 187 |
numbers.put(state, thisNodeNumber); |
| 188 |
|
| 189 |
return true; |
| 190 |
} |
| 191 |
}); |
| 192 |
|
| 193 |
return numbers; |
| 194 |
} |
| 195 |
} |