src/com/hughes/android/dictionary/IndexBuilder.java

   1 package com.hughes.android.dictionary;\r
   2 \r
   3 import java.io.IOException;\r
   4 import java.io.RandomAccessFile;\r
   5 import java.io.Serializable;\r
   6 import java.util.ArrayList;\r
   7 import java.util.Collections;\r
   8 import java.util.LinkedHashSet;\r
   9 import java.util.List;\r
  10 import java.util.Map;\r
  11 import java.util.Set;\r
  12 import java.util.TreeMap;\r
  13 import java.util.regex.Pattern;\r
  14 \r
  15 import com.hughes.util.FileUtil;\r
  16 \r
  17 public class IndexBuilder {\r
  18 \r
  19   static final Pattern WHITESPACE = Pattern.compile("\\s+");\r
  20   static final Pattern NONALPHA = Pattern.compile("[^A-Za-z]+");\r
  21 \r
  22   public static void main(String[] args) throws IOException,\r
  23       ClassNotFoundException {\r
  24     if (args.length != 1) {\r
  25       System.err.println("No input file.");\r
  26       return;\r
  27     }\r
  28 \r
  29     final String file = args[0];\r
  30     final byte lang = Entry.LANG1;\r
  31     Node rootBuilder;\r
  32     rootBuilder = createIndex(file, lang);\r
  33     FileUtil.write(rootBuilder, String.format("%s_builder_%d.serialized", file, lang));\r
  34     rootBuilder = (Node) FileUtil.read(String.format("%s_builder_%d.serialized", file, lang));\r
  35 \r
  36     rootBuilder.forEachNode(new Function<Node>() {\r
  37       @Override\r
  38       public void invoke(final Node node) {\r
  39         for (final List<EntryDescriptor> entryDescriptors : node.entries.values()) {\r
  40           Collections.sort(entryDescriptors);\r
  41         }\r
  42       }});\r
  43     \r
  44     // Dump twice to get accurate file locations.\r
  45     for (int i = 0; i < 2; ++i) {\r
  46       final RandomAccessFile raf = new RandomAccessFile(String.format(Dictionary.INDEX_FORMAT, file, lang), "rw"); \r
  47       rootBuilder.dump(raf);\r
  48       raf.close();\r
  49     }\r
  50     \r
  51   }\r
  52 \r
  53   // ----------------------------------------------------------------\r
  54   \r
  55   static final class EntryDescriptor implements Comparable<EntryDescriptor>, Serializable {\r
  56     final int offset;\r
  57     final int numTokens;\r
  58     public EntryDescriptor(int offset, int numTokens) {\r
  59       this.offset = offset;\r
  60       this.numTokens = numTokens;\r
  61     }\r
  62     @Override\r
  63     public boolean equals(Object obj) {\r
  64       final EntryDescriptor that = (EntryDescriptor) obj;\r
  65       return this.offset == that.offset;\r
  66     }\r
  67     @Override\r
  68     public int hashCode() {\r
  69       return offset;\r
  70     }\r
  71     @Override\r
  72     public int compareTo(EntryDescriptor o) {\r
  73       return this.numTokens < o.numTokens ? -1 : this.numTokens == o.numTokens ? 0 : 1;\r
  74     }\r
  75   }\r
  76 \r
  77   static final class Node implements Serializable {\r
  78     final String normalizedWord;\r
  79     \r
  80     final TreeMap<String, Node> children = new TreeMap<String, Node>();\r
  81     final TreeMap<String,List<EntryDescriptor>> entries = new TreeMap<String, List<EntryDescriptor>>();\r
  82     \r
  83 //    final List<EntryDescriptor> offsets = new ArrayList<EntryDescriptor>();\r
  84     \r
  85     int descendantOffsetCount = 0;\r
  86     \r
  87     int indexFileLocation = -1;\r
  88 \r
  89     public Node(final String normalizedWord) {\r
  90       if (normalizedWord.length() == 0) {\r
  91         System.out.println("Created root.");\r
  92       }\r
  93       this.normalizedWord = normalizedWord.intern();\r
  94     }\r
  95 \r
  96     public Node getNode(final String nWord, final int pos,\r
  97         final boolean create) {\r
  98       assert this.normalizedWord.equals(nWord.substring(0, pos));\r
  99 \r
 100       if (pos == nWord.length()) {\r
 101         assert normalizedWord.equals(nWord);\r
 102         return this;\r
 103       }\r
 104 \r
 105       final String rest = nWord.substring(pos);\r
 106       assert rest.length() > 0;\r
 107 \r
 108       final Map.Entry<String, Node> lcsEntry;\r
 109       final String lcs;\r
 110       {\r
 111         final Map.Entry<String, Node> floorEntry = children.floorEntry(rest);\r
 112         final Map.Entry<String, Node> ceilingEntry = children\r
 113             .ceilingEntry(rest);\r
 114         final String floorLcs = floorEntry == null ? "" : StringUtil\r
 115             .longestCommonSubstring(rest, floorEntry.getKey());\r
 116         final String ceilingLcs = ceilingEntry == null ? "" : StringUtil\r
 117             .longestCommonSubstring(rest, ceilingEntry.getKey());\r
 118         if (floorLcs.length() > ceilingLcs.length()) {\r
 119           lcsEntry = floorEntry;\r
 120           lcs = floorLcs;\r
 121         } else {\r
 122           lcsEntry = ceilingEntry;\r
 123           lcs = ceilingLcs;\r
 124         }\r
 125       }\r
 126 \r
 127       // No LCS, have to add everything.\r
 128       if (lcs.length() == 0) {\r
 129         if (!create) {\r
 130           return null;\r
 131         }\r
 132         final Node result = new Node(nWord);\r
 133         final Object old = children.put(rest.intern(), result);\r
 134         assert old == null;\r
 135         // System.out.println("  Adding final chunk: " + rest);\r
 136         return result;\r
 137       }\r
 138 \r
 139       assert lcsEntry != null;\r
 140 \r
 141       // The map already contained the LCS.\r
 142       if (lcs.length() == lcsEntry.getKey().length()) {\r
 143         assert lcs.equals(lcsEntry.getKey());\r
 144         final Node result = lcsEntry.getValue().getNode(nWord,\r
 145             pos + lcs.length(), create);\r
 146         assert result.normalizedWord.equals(nWord);\r
 147         return result;\r
 148       }\r
 149 \r
 150       if (!create) {\r
 151         return null;\r
 152       }\r
 153 \r
 154       // Have to split, inserting the LCS.\r
 155       // System.out.println("  Splitting " + lcsEntry + "/" + word + " @ " +\r
 156       // lcs);\r
 157       final Node newChild = new Node(nWord.substring(0, pos + lcs.length()));\r
 158       final Object old = children.put(lcs.intern(), newChild);\r
 159       assert old == null;\r
 160       children.remove(lcsEntry.getKey());\r
 161       newChild.children.put(lcsEntry.getKey().substring(lcs.length())\r
 162           .intern(), lcsEntry.getValue());\r
 163 \r
 164       if (lcs.equals(rest)) {\r
 165         return newChild;\r
 166       }\r
 167       final Node result = new Node(nWord);\r
 168       final Object old2 = newChild.children.put(rest.substring(lcs.length())\r
 169           .intern(), result);\r
 170       assert old2 == null;\r
 171       // System.out.println("  newchildren=" + newChild.children);\r
 172 \r
 173       return result;\r
 174     }\r
 175 \r
 176     void forEachNode(final Function<Node> f) {\r
 177       f.invoke(this);\r
 178       for (final Node child : children.values()) {\r
 179         child.forEachNode(f);\r
 180       }\r
 181     }\r
 182 \r
 183     int descendantCount() {\r
 184       int count = 1;\r
 185       for (final Node child : children.values()) {\r
 186         count += child.descendantCount();\r
 187       }\r
 188       return count;\r
 189     }\r
 190 \r
 191     void recursiveSetDescendantOffsetCount() {\r
 192       descendantOffsetCount = offsets.size();\r
 193       for (final Node child : children.values()) {\r
 194         child.recursiveSetDescendantOffsetCount();\r
 195         descendantOffsetCount += child.descendantOffsetCount;\r
 196       }\r
 197     }\r
 198 \r
 199     @Override\r
 200     public String toString() {\r
 201       return normalizedWord + ":" + offsets.size();\r
 202     }\r
 203     \r
 204     void dump(final RandomAccessFile file) throws IOException {\r
 205       if (indexFileLocation == -1) {\r
 206         indexFileLocation = (int) file.getFilePointer();\r
 207       } else {\r
 208         assert indexFileLocation == file.getFilePointer();\r
 209       }\r
 210       \r
 211       // Children.\r
 212       file.writeInt(children.size());\r
 213       for (final Map.Entry<String, Node> child : children.entrySet()) {\r
 214         file.writeUTF(child.getKey());\r
 215         file.writeInt(child.getValue().indexFileLocation);\r
 216       }\r
 217       \r
 218       // Offsets.\r
 219       file.writeInt(offsets.size());\r
 220       for (int i = 0; i < offsets.size(); i++) {\r
 221         file.writeInt(offsets.get(i).offset);\r
 222       }\r
 223       \r
 224       // Dump children.\r
 225       for (final Map.Entry<String, Node> child : children.entrySet()) {\r
 226         child.getValue().dump(file);\r
 227       }\r
 228     }\r
 229   }\r
 230 \r
 231   // ----------------------------------------------------------------\r
 232 \r
 233   static Node createIndex(final String file, final byte lang) throws IOException {\r
 234     final Node root = new Node("");\r
 235     final RandomAccessFile raf = new RandomAccessFile(file, "r");\r
 236     String line;\r
 237     final Entry entry = new Entry();\r
 238     int lineCount = 0;\r
 239     long fileLocation = 0;\r
 240     while ((line = raf.readLine()) != null) {\r
 241       assert ((int) fileLocation) == fileLocation;\r
 242 \r
 243       line = line.trim();\r
 244       if (line.isEmpty() || line.startsWith("#") || !entry.parseFromLine(line)) {\r
 245         continue;\r
 246       }\r
 247       final String text = entry.getIndexableText(Entry.LANG1);\r
 248       final String[] tokens = WHITESPACE.split(text);\r
 249       final Set<String> tokenSet = new LinkedHashSet<String>();\r
 250       for (String token : tokens) {\r
 251         if (token.length() <= 1 || !Character.isLetter(token.charAt(0))) {\r
 252           continue;\r
 253         }\r
 254         tokenSet.add(EntryFactory.entryFactory.normalizeToken(token, lang));\r
 255       }\r
 256       for (final String normalized : tokenSet) {\r
 257         // System.out.println("Inserting: " + normalized);\r
 258         if ("die".equals(normalized) || "eine".equals(normalized)) {\r
 259           // System.out.println("hello");\r
 260         }\r
 261         final Node node = root.getNode(normalized, 0, true);\r
 262         node.offsets.add(new EntryDescriptor((int) fileLocation, tokens.length));\r
 263         assert node == root.getNode(normalized, 0, false);\r
 264         assert normalized\r
 265             .equals(root.getNode(normalized, 0, false).normalizedWord);\r
 266       }\r
 267 \r
 268       if (lineCount % 10000 == 0) {\r
 269         System.out.println("IndexBuilder: " + "lineCount=" + lineCount);\r
 270       }\r
 271       \r
 272       lineCount++;\r
 273       fileLocation = raf.getFilePointer();\r
 274     }\r
 275     raf.close();\r
 276     return root;\r
 277   }\r
 278 \r
 279 }\r