import java.util.*; import java.io.*; class StackEntry { int uInputPos; //stores our position in the input vector.. int uState; //stores the next state for understanding where we are in the graph. boolean ValidOutput; int OutputSymbol; int OutputLength; StackEntry Parent; StackEntry(int uInput, int uNext, boolean OutputValid, int OutSymbol, int OLength, StackEntry ParentEntry ){ uInputPos = uInput; uState = uNext; ValidOutput = OutputValid; OutputSymbol = OutSymbol; OutputLength = OLength; Parent = ParentEntry; } int InputPos(){ return(uInputPos); } int NextState(){ return(uState); } boolean OutputValid(){ return(ValidOutput); } int OutSymbol() { return (OutputSymbol); } int OutputLength(){ return (OutputLength); } StackEntry Parent(){ return (Parent); } } //The following class is for handling the bogus integer format in the binary //transducer files //Integers in these files are in the form 0xabcdefgh and represent the //value 0xefghabcd class FunkyIntegerReader { static final int N256 = 256, N65536 = 65536; static int FunkyReadInteger(DataInputStream TransducerFileHandle){ int Lower, Upper; try{ Lower = (int) TransducerFileHandle.readChar(); Lower = (Lower % N256) * N256 + Lower / N256; Upper = (int) TransducerFileHandle.readChar(); Upper = (Upper % N256) * N256 + Upper / N256; return ((int) (Upper * N65536 + Lower)); } catch (IOException e) { System.out.println("I/O Error in FunkyReadInteger"); return (-1); // tentative error return } } } class ByteStreamConverter{ static int TwoBytesToShort(byte BLow, byte BHigh){ int Low = (((char)BLow) & 255); int High = (((char)BHigh) & 255); return((Low + (High<<8))); } static int FourBytesToInt(byte BLow1, byte BHigh1,byte BLow2, byte BHigh2){ int Low1 = (((char)BLow1) & 255); int High1 = (((char)BHigh1) & 255); int Low = (Low1 + (High1<<8)); int Low2 = (((char)BLow2) & 255); int High2 = (((char)BHigh2) & 255); int High = (Low2 + (High2<<8)); return ((int)(Low + (High<<16))); } } /** * @author oflazer * */ public class FSTransducer { private int m_nVertexNum;//the number of vertices . private int m_nArcNum;//the number of arcs . private int m_nSymbolNum;//size of the symbol table private int m_nInitialSymbolNum;//number of symbols in the original symbol table private static final short Q_MARK = (short) 0xffff; boolean[] Final; short [] OutDegree; int [] ArcOffset; short[] ArcUpperSymbol; short[] ArcLowerSymbol; int[] ArcNextState; private Hashtable ExtToInt; private String[] IntToExt; //public methods public FSTransducer(String BinaryTransducerFile) throws FSTransducerException { try{ DataInputStream TransducerFile = new DataInputStream(new FileInputStream(BinaryTransducerFile)); String sFileType = ""; String sOptimizeDir = ""; int uTableSize, uInternal=0; int nSymbolLength; int FileOffset = 0; //read the three bytes for file descriptor sFileType = sFileType + (char) TransducerFile.readByte(); sFileType = sFileType + (char) TransducerFile.readByte(); sFileType = sFileType + (char) TransducerFile.readByte(); //if it is a bogus file raise an exception if (!sFileType.equals("FST")){ throw new FSTransducerException("Invalid binary File"); } // read the byte for lookup optimize direction sOptimizeDir = sOptimizeDir + (char) TransducerFile.readByte(); //System.out.println("FileType OK "+ sFileType); FileOffset +=4; if(sOptimizeDir.equals("l")){ //m_bIsLowOptimized = true; } else { //m_bIsLowOptimized = false; } // read transducer and symbol table parameters m_nVertexNum = FunkyIntegerReader.FunkyReadInteger(TransducerFile); m_nArcNum = FunkyIntegerReader.FunkyReadInteger(TransducerFile); uTableSize = FunkyIntegerReader.FunkyReadInteger(TransducerFile); //System.out.println(m_nVertexNum + " States " + m_nArcNum + " Arcs " + uTableSize + " Symbols"); FileOffset+=12; m_nSymbolNum = uTableSize + 1 ; // 1 additional symbol for the "?" symbol m_nInitialSymbolNum = uTableSize; // create Vertex table //Vertices = new VertexEntry[m_nVertexNum]; Final = new boolean[m_nVertexNum]; OutDegree = new short [m_nVertexNum]; ArcOffset = new int[m_nVertexNum]; ArcUpperSymbol = new short[m_nArcNum]; ArcLowerSymbol = new short[m_nArcNum]; ArcNextState = new int [m_nArcNum]; //Arcs = new ArcEntry[m_nArcNum]; // construct symbol table to/from internal code mapping tables IntToExt = new String[100*m_nSymbolNum];// addition entries for unknown symbols ExtToInt = new Hashtable(4096); // read in the symbol table and set up mapping tables //System.out.println("Symbol Mapping Table"); for (int k=0; k < uTableSize; k++){ //sSymbol = new String(""); nSymbolLength = FunkyIntegerReader.FunkyReadInteger(TransducerFile); byte isobytes[] = new byte[nSymbolLength]; FileOffset+=4; for (int l = 0; l < nSymbolLength; l++){ //sSymbol = sSymbol + (char) TransducerFile.readByte(); isobytes[l] = TransducerFile.readByte(); FileOffset+=1; } String isostring = new String(isobytes,"iso-8859-9"); //System.out.println("Symbol " + sSymbol); // if (!isostring.equals("?")) { IntToExt[++uInternal] = isostring; ExtToInt.put(new String(isostring),new Integer(uInternal)); //System.out.println("Symbol " + isostring + " " + IntToExt[uInternal] + " Length " + nSymbolLength + " Internal " + ExtToInt.get(isostring)); } } //System.out.println("FileOffset now " + FileOffset); //we have now read the symbol table int maxbuffersize = m_nVertexNum; if(maxbuffersize < m_nArcNum) { maxbuffersize = m_nArcNum; } //System.out.println("Allocated "+ 8*maxbuffersize + " bytes for I/O buffer"); byte [] Buffer = new byte[8*maxbuffersize]; TransducerFile.read(Buffer,0,8*m_nVertexNum); FileOffset+=8*m_nVertexNum; //System.out.println("Read the state info"); short Fanout; //boolean IsFinal ; int Offset; int Low, High, Low1, High1, Low2, High2; for (int s=0; s < m_nVertexNum; s++){ int s8= s << 3; { // this is inlined code for this Low = (((char)Buffer[s8]) & 255); High = (((char)Buffer[s8+1]) & 255); Fanout = (short)(Low + (High<<8)); } if (Fanout % 2 == 0) {Final[s] = false;} else { Final[s] = true; } OutDegree[s] = (short)(Fanout >> 1); { Low1 = (((char)Buffer[s8+4]) & 255); High1 = (((char)Buffer[s8+5]) & 255); Low = (Low1 + (High1<<8)); Low2 = (((char)Buffer[s8+6]) & 255); High2 = (((char)Buffer[s8+7]) & 255); High = (Low2 + (High2<<8)); Offset= (int)(Low + (High<<16)); } //Vertices[s]= new VertexEntry(IsFinal,Fanout,Offset); ArcOffset[s]= Offset; } //System.out.println("Vertices are set up"); // note that we are reusing the buffer for arcs also TransducerFile.read(Buffer,0,8*m_nArcNum); FileOffset+=8*m_nArcNum; //System.out.println("Read the arc info"); //System.out.println("FileOffset now " + FileOffset); short Upper, Lower; int NextState; for (int a=0; a < m_nArcNum ; a++){ int a8 = a << 3; //if(Buffer[a8] == 0xff ){System.out.println("Question Mark "+Buffer[a8]);} // Inlined code for (short)ByteStreamConverter.TwoBytesToShort(Buffer[a8],Buffer[a8+1]) Low = (((char)Buffer[a8]) & 255); High = (((char)Buffer[a8+1]) & 255); Upper = (short)(Low + (High<<8)); // Inlined code for (short)ByteStreamConverter.TwoBytesToShort(Buffer[a8+2],Buffer[a8+3]) Low = (((char)Buffer[a8+2]) & 255); High = (((char)Buffer[a8+3]) & 255); Lower = (short)(Low + (High<<8)); // Inlined code for ByteStreamConverter.FourBytesToInt(Buffer[a8+4],Buffer[a8+5],Buffer[a8+6],Buffer[a8+7]) Low1 = (((char)Buffer[a8+4]) & 255); High1 = (((char)Buffer[a8+5]) & 255); Low = (Low1 + (High1<<8)); Low2 = (((char)Buffer[a8+6]) & 255); High2 = (((char)Buffer[a8+7]) & 255); High = (Low2 + (High2<<8)); NextState= (int)(Low + (High<<16)); ArcUpperSymbol[a] = Upper; ArcLowerSymbol[a] = Lower; ArcNextState[a] = NextState; //Arcs[a]= new ArcEntry( Upper, Lower, NextState); //if ( Arcs[a].uLower < 0 || Arcs[a].uUpper < 0 || Arcs[a].uNextState < 0) System.out.println("Problem at arc "+ a + " "+Arcs[a].uLower+" "+Arcs[a].uUpper + " "+Arcs[a].uNextState); } //System.out.println("Arcs are set up"); //System.out.println("Transducer read from the file"); System.runFinalization(); System.gc(); //System.out.println("Transducer object now constructed"); } catch (IOException e) { System.out.println("I/O Error in FSTransducer Constructor"); } } public LinkedList Look(String sInputString, int Direction, boolean Greedy){ LinkedList ResultStrings = new LinkedList(); int nInputLength = sInputString.length(); int subOutputIndex = 0; int[] outputBuffer = new int[1024]; int Start = 0; int End; String Symbol; if (Greedy){ // makes O(n^2) hash queries - while(Start < nInputLength){ End = nInputLength; // check all substrings in decreasing length to see if it is in the symbol table // substring generation could perhaps be sped up!!!! while(Start < End && !ExtToInt.containsKey(sInputString.substring(Start,End))) { End--; } Symbol = sInputString.substring(Start,End); if (Start < End){ // This implies that sum substring was found in the symbol table - some lookup succeeded //System.out.println("Found Symbol "+ sInputString.substring(Start,End)); // transfer the internal code to the internal symbol buffer outputBuffer[subOutputIndex++] = ((Integer)(ExtToInt.get(sInputString.substring(Start,End)))).intValue(); Start = End; } else { // if we are here then no substring was found in the symbol table - all lookups failed // there is an unknown symbol of length 1 at location Start // extract the symbol and add it to the symbol table (temporarily for this session) Symbol = sInputString.substring(Start,End+1); // System.out.println("Start " + Start + " End " + End + " UnknownSymbol "+ Symbol); ExtToInt.put(new String(Symbol),new Integer(m_nSymbolNum)); IntToExt[m_nSymbolNum]=Symbol; // Check for possible overflow here m_nSymbolNum++; outputBuffer[subOutputIndex++] = ((Integer)(ExtToInt.get(Symbol))).intValue(); // could be sped up Start ++; } } } else { // Not greedy all combinations have to be produced -- we need to use a chart-based system here } // Now call look up/down LinkedList Results = Look(outputBuffer, subOutputIndex, Direction); ListIterator Result = Results.listIterator(); int ResultLength; int[] Out; String OutputString; // We need to write this a bit more efficienty using string buffer // need to know how long the buffer should be // translate internal symbols to external symbols and add the resulting string to the return list // todo rewrite with string buffer while(Result.hasNext()){ OutputString = ""; Out = ((int [])(Result.next())); ResultLength = Out.length; for (int j=0; j < ResultLength; j++){ OutputString = OutputString +IntToExt[Out[j]];// this is concatenation and is ugly!! } ResultStrings.addFirst(OutputString); } return (ResultStrings); } /* stll to do. If input side is not ? but output side is ? * we need to produce the symbole ? on the output */ private LinkedList Look(int[] Input, int InputLength, int Direction) { LinkedList Results = new LinkedList(); Stack StateStack = new Stack(); StackEntry Current, OutputCursor; int InputSymbol; int LookSideSymbol; int OutputSideSymbol; //ArcEntry Arc; int ArcsStart, ArcsEnd; int OutputLength; StateStack.push(new StackEntry(0, 0, false, 0, 0, null)); while(!StateStack.isEmpty()){ Current=(StackEntry)StateStack.pop(); // if the current state is a final state and the input string is exhausted if(InputLength == Current.uInputPos) { // if we are at a final state then // add output string to the return list if (Final[Current.uState]){ // traverse from this state back to root and create the output string OutputLength = Current.OutputLength; int [] Output= new int[OutputLength]; int OutputPos = OutputLength; OutputCursor = Current; while(OutputCursor != null){ if(OutputCursor.ValidOutput){ Output[--OutputPos]= OutputCursor.OutputSymbol; } OutputCursor = OutputCursor.Parent; } Results.addFirst(Output); } else { // input is exhausted and we at a notfinal state ; do nothing } // if current state has any epsilon transitions for the look direction ArcsStart = ArcOffset[Current.NextState()]; ArcsEnd = ArcsStart + OutDegree[Current.uState];//actually one more for (int a = ArcsStart; a < ArcsEnd; a++) {// //Arc = Arcs[a]; OutputSideSymbol = ((Direction == 1) ? ArcUpperSymbol[a]:ArcLowerSymbol[a]); LookSideSymbol = ((Direction == 1) ? ArcLowerSymbol[a]:ArcUpperSymbol[a]); if (LookSideSymbol == 0) { // lower/upper symbol is epsilon StateStack.push(new StackEntry(Current.uInputPos,// input does not move ArcNextState[a],// we move to the next state true, // we have valid output symbol OutputSideSymbol, // the output symbol Current.OutputLength+1, Current)); // the parent stack entry handle } } } else if (InputLength > Current.uInputPos){ // input is not exhausted InputSymbol = Input[Current.uInputPos]; if ( InputSymbol <= m_nInitialSymbolNum) { /* input is a known symbol */ // for all input arcs that match the current input symbol // create a copy of the Output, push the corresponding output symbol // if not empty onto the copy of the output and // push a new stack entry with the input position incremented by one // the new next state and the augmented output ArcsStart = ArcOffset[Current.uState]; ArcsEnd = ArcsStart + OutDegree[Current.uState];//actually one more for (int a = ArcsStart; a < ArcsEnd; a++) {// //Arc = Arcs[a]; OutputSideSymbol = ((Direction == 1) ? ArcUpperSymbol[a]:ArcLowerSymbol[a]); LookSideSymbol = ((Direction == 1) ? ArcLowerSymbol[a]:ArcUpperSymbol[a]); if (LookSideSymbol == InputSymbol) { // lower/upper symbol is not epsilon StateStack.push(new StackEntry(Current.uInputPos+1,// input moves by one ArcNextState[a],// we move to the next state (OutputSideSymbol == 0) ? false : true, // we have valid output symbol OutputSideSymbol, // the output symbol (OutputSideSymbol == 0) ? Current.OutputLength:Current.OutputLength+1, Current)); // the parent stack entry handle } else if (LookSideSymbol == 0) { // lower/upper symbol is epsilon StateStack.push(new StackEntry(Current.uInputPos,// input does not move ArcNextState[a],// we move to the next state true, // we have valid output symbol OutputSideSymbol, // the output symbol Current.OutputLength+1, Current)); // the parent stack entry handle } } } // do the same for any transitions on the input side that have // epsilon as their symbol // do the same as above but do NOT move the input pointer else { /* input is NOT a known symbol */ // for all input arcs that have a ? on the input side // create a copy of the Output, push the corresponding output symbol // if not empty onto the copy of the output and // push a new stack entry with the input position incremented by one // the new next state and the augmented output // do the same for any transitions on the input side that have // epsilon as their symbol // do the same as above but do NOT move the input pointer ArcsStart = ArcOffset[Current.uState]; ArcsEnd = ArcsStart + OutDegree[Current.uState];//actually one more for (int a = ArcsStart; a < ArcsEnd; a++) {// //Arc = Arcs[a]; OutputSideSymbol = ((Direction == 1) ? ArcUpperSymbol[a]:ArcLowerSymbol[a]); LookSideSymbol = ((Direction == 1) ? ArcLowerSymbol[a]:ArcUpperSymbol[a]); if (LookSideSymbol == Q_MARK) { // lower/upper symbol matches question mark StateStack.push(new StackEntry(Current.uInputPos+1,// input moves by one ArcNextState[a],// we move to the next state (OutputSideSymbol == 0) ? false : true, // we have valid output symbol (OutputSideSymbol == Q_MARK) ? InputSymbol: OutputSideSymbol,// the output symbol is the same as Input since Input is ? (OutputSideSymbol == 0) ? Current.OutputLength:Current.OutputLength+1, Current)); // the parent stack entry handle } else if (LookSideSymbol == 0) { // lower/upper symbol is epsilon StateStack.push(new StackEntry(Current.uInputPos,// input does not move ArcNextState[a],// we move to the next state true, // we have valid output symbol OutputSideSymbol, // the output symbol Current.OutputLength+1, Current)); // the parent stack entry handle } } } } } // Stack is now empty; return the list of output strings return(Results); } }