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 //    final AtomicInteger c = new AtomicInteger();\r
  37     rootBuilder.forEachNode(new Function<Node>() {\r
  38       @Override\r
  39       public void invoke(Node t) {\r
  40         Collections.sort(t.offsets);\r
  41 //        if (t.offsets.size() > 128) {\r
  42 //          System.out.println(t);\r
  43 //          c.incrementAndGet();\r
  44 //        }\r
  45       }});\r
  46 //    System.out.println(c);\r
  47     \r
  48 //    rootBuilder.recursiveSetDescendantOffsetCount();\r
  49 //    rootBuilder.packDescendants(128);\r
  50 \r
  51     // Dump twice to get accurate file locations.\r
  52     for (int i = 0; i < 2; ++i) {\r
  53       final RandomAccessFile raf = new RandomAccessFile(String.format(Dictionary.INDEX_FORMAT, file, lang), "rw"); \r
  54       rootBuilder.dump(raf);\r
  55       raf.close();\r
  56     }\r
  57     \r
  58   }\r
  59 \r
  60   // ----------------------------------------------------------------\r
  61   \r
  62   static final class EntryDescriptor implements Comparable<EntryDescriptor>, Serializable {\r
  63     final int offset;\r
  64     final int numTokens;\r
  65     public EntryDescriptor(int offset, int numTokens) {\r
  66       this.offset = offset;\r
  67       this.numTokens = numTokens;\r
  68     }\r
  69     @Override\r
  70     public boolean equals(Object obj) {\r
  71       final EntryDescriptor that = (EntryDescriptor) obj;\r
  72       return this.offset == that.offset;\r
  73     }\r
  74     @Override\r
  75     public int hashCode() {\r
  76       return offset;\r
  77     }\r
  78     @Override\r
  79     public int compareTo(EntryDescriptor o) {\r
  80       return this.numTokens < o.numTokens ? -1 : this.numTokens == o.numTokens ? 0 : 1;\r
  81     }\r
  82   }\r
  83 \r
  84   static final class Node implements Serializable {\r
  85     private static final long serialVersionUID = -5423134653901704956L;\r
  86     \r
  87     final TreeMap<String, Node> children = new TreeMap<String, Node>();\r
  88     final List<EntryDescriptor> offsets = new ArrayList<EntryDescriptor>();\r
  89     final String sequence;\r
  90     \r
  91     int descendantOffsetCount = 0;\r
  92     \r
  93     int indexFileLocation = -1;\r
  94 \r
  95     public Node(String sequence) {\r
  96       if (sequence.length() == 0) {\r
  97         System.out.println("Created root.");\r
  98       }\r
  99       this.sequence = sequence.intern();\r
 100     }\r
 101 \r
 102     public Node getIndexNode(final String word, final int pos,\r
 103         final boolean create) {\r
 104       assert this.sequence.equals(word.substring(0, pos));\r
 105 \r
 106       if (pos == word.length()) {\r
 107         assert sequence.equals(word);\r
 108         return this;\r
 109       }\r
 110 \r
 111       final String rest = word.substring(pos);\r
 112       assert rest.length() > 0;\r
 113 \r
 114       final Map.Entry<String, Node> lcsEntry;\r
 115       final String lcs;\r
 116       {\r
 117         final Map.Entry<String, Node> floorEntry = children.floorEntry(rest);\r
 118         final Map.Entry<String, Node> ceilingEntry = children\r
 119             .ceilingEntry(rest);\r
 120         final String floorLcs = floorEntry == null ? "" : StringUtil\r
 121             .longestCommonSubstring(rest, floorEntry.getKey());\r
 122         final String ceilingLcs = ceilingEntry == null ? "" : StringUtil\r
 123             .longestCommonSubstring(rest, ceilingEntry.getKey());\r
 124         if (floorLcs.length() > ceilingLcs.length()) {\r
 125           lcsEntry = floorEntry;\r
 126           lcs = floorLcs;\r
 127         } else {\r
 128           lcsEntry = ceilingEntry;\r
 129           lcs = ceilingLcs;\r
 130         }\r
 131       }\r
 132 \r
 133       // No LCS, have to add everything.\r
 134       if (lcs.length() == 0) {\r
 135         if (!create) {\r
 136           return null;\r
 137         }\r
 138         final Node result = new Node(word);\r
 139         final Object old = children.put(rest.intern(), result);\r
 140         assert old == null;\r
 141         // System.out.println("  Adding final chunk: " + rest);\r
 142         return result;\r
 143       }\r
 144 \r
 145       assert lcsEntry != null;\r
 146 \r
 147       // The map already contained the LCS.\r
 148       if (lcs.length() == lcsEntry.getKey().length()) {\r
 149         assert lcs.equals(lcsEntry.getKey());\r
 150         final Node result = lcsEntry.getValue().getIndexNode(word,\r
 151             pos + lcs.length(), create);\r
 152         assert result.sequence.equals(word);\r
 153         return result;\r
 154       }\r
 155 \r
 156       if (!create) {\r
 157         return null;\r
 158       }\r
 159 \r
 160       // Have to split, inserting the LCS.\r
 161       // System.out.println("  Splitting " + lcsEntry + "/" + word + " @ " +\r
 162       // lcs);\r
 163       final Node newChild = new Node(word.substring(0, pos + lcs.length()));\r
 164       final Object old = children.put(lcs.intern(), newChild);\r
 165       assert old == null;\r
 166       children.remove(lcsEntry.getKey());\r
 167       newChild.children.put(lcsEntry.getKey().substring(lcs.length())\r
 168           .intern(), lcsEntry.getValue());\r
 169 \r
 170       if (lcs.equals(rest)) {\r
 171         return newChild;\r
 172       }\r
 173       final Node result = new Node(word);\r
 174       final Object old2 = newChild.children.put(rest.substring(lcs.length())\r
 175           .intern(), result);\r
 176       assert old2 == null;\r
 177       // System.out.println("  newchildren=" + newChild.children);\r
 178 \r
 179       return result;\r
 180     }\r
 181 \r
 182     MemoryIndex.Node toIndexNode() {\r
 183       final MemoryIndex.Node result = new MemoryIndex.Node(children.size(), offsets\r
 184           .size());\r
 185       int i = 0;\r
 186       for (final Map.Entry<String, Node> entry : children.entrySet()) {\r
 187         result.chars[i] = entry.getKey();\r
 188         result.children[i] = entry.getValue().toIndexNode();\r
 189         i++;\r
 190       }\r
 191       return result;\r
 192     }\r
 193 \r
 194     void forEachNode(final Function<Node> f) {\r
 195       f.invoke(this);\r
 196       for (final Node child : children.values()) {\r
 197         child.forEachNode(f);\r
 198       }\r
 199     }\r
 200 \r
 201     int descendantCount() {\r
 202       int count = 1;\r
 203       for (final Node child : children.values()) {\r
 204         count += child.descendantCount();\r
 205       }\r
 206       return count;\r
 207     }\r
 208 \r
 209     void recursiveSetDescendantOffsetCount() {\r
 210       descendantOffsetCount = offsets.size();\r
 211       for (final Node child : children.values()) {\r
 212         child.recursiveSetDescendantOffsetCount();\r
 213         descendantOffsetCount += child.descendantOffsetCount;\r
 214       }\r
 215     }\r
 216 \r
 217     public void packDescendants(final int maxDescendants) {\r
 218       if (descendantOffsetCount <= maxDescendants) {\r
 219         final Set<EntryDescriptor> descendantOffsets = new LinkedHashSet<EntryDescriptor>();\r
 220         recursiveAddDescendants(descendantOffsets);\r
 221         assert descendantOffsets.size() <= maxDescendants;\r
 222         offsets.clear();\r
 223         offsets.addAll(descendantOffsets);\r
 224         children.clear();\r
 225       } else {\r
 226         for (final Node child : children.values()) {\r
 227           child.packDescendants(maxDescendants);\r
 228         }\r
 229       }\r
 230     }\r
 231 \r
 232     private void recursiveAddDescendants(final Set<EntryDescriptor> descendantOffsets) {\r
 233       descendantOffsets.addAll(this.offsets);\r
 234       for (final Node child : children.values()) {\r
 235         child.recursiveAddDescendants(descendantOffsets);\r
 236       }\r
 237     }\r
 238 \r
 239     @Override\r
 240     public String toString() {\r
 241       return sequence + ":" + offsets.size();\r
 242     }\r
 243     \r
 244     void dump(final RandomAccessFile file) throws IOException {\r
 245       if (indexFileLocation == -1) {\r
 246         indexFileLocation = (int) file.getFilePointer();\r
 247       } else {\r
 248         assert indexFileLocation == file.getFilePointer();\r
 249       }\r
 250       \r
 251       // Children.\r
 252       file.writeInt(children.size());\r
 253       for (final Map.Entry<String, Node> child : children.entrySet()) {\r
 254         file.writeUTF(child.getKey());\r
 255         file.writeInt(child.getValue().indexFileLocation);\r
 256       }\r
 257       \r
 258       // Offsets.\r
 259       file.writeInt(offsets.size());\r
 260       for (int i = 0; i < offsets.size(); i++) {\r
 261         file.writeInt(offsets.get(i).offset);\r
 262       }\r
 263       \r
 264       // Dump children.\r
 265       for (final Map.Entry<String, Node> child : children.entrySet()) {\r
 266         child.getValue().dump(file);\r
 267       }\r
 268     }\r
 269   }\r
 270 \r
 271   // ----------------------------------------------------------------\r
 272 \r
 273   static Node createIndex(final String file, final byte lang) throws IOException {\r
 274     final Node root = new Node("");\r
 275     final RandomAccessFile raf = new RandomAccessFile(file, "r");\r
 276     String line;\r
 277     final Entry entry = new Entry();\r
 278     int lineCount = 0;\r
 279     long fileLocation = 0;\r
 280     while ((line = raf.readLine()) != null) {\r
 281       assert ((int) fileLocation) == fileLocation;\r
 282 \r
 283       line = line.trim();\r
 284       if (line.isEmpty() || line.startsWith("#") || !entry.parseFromLine(line)) {\r
 285         continue;\r
 286       }\r
 287       final String text = entry.getIndexableText(Entry.LANG1);\r
 288       final String[] tokens = WHITESPACE.split(text);\r
 289       final Set<String> tokenSet = new LinkedHashSet<String>();\r
 290       for (String token : tokens) {\r
 291         if (token.length() <= 1 || !Character.isLetter(token.charAt(0))) {\r
 292           continue;\r
 293         }\r
 294         tokenSet.add(entry.normalizeToken(token, lang));\r
 295       }\r
 296       for (final String normalized : tokenSet) {\r
 297         // System.out.println("Inserting: " + normalized);\r
 298         if ("die".equals(normalized) || "eine".equals(normalized)) {\r
 299           // System.out.println("hello");\r
 300         }\r
 301         final Node node = root.getIndexNode(normalized, 0, true);\r
 302         node.offsets.add(new EntryDescriptor((int) fileLocation, tokens.length));\r
 303         assert node == root.getIndexNode(normalized, 0, false);\r
 304         assert normalized\r
 305             .equals(root.getIndexNode(normalized, 0, false).sequence);\r
 306       }\r
 307 \r
 308       if (lineCount % 10000 == 0) {\r
 309         System.out.println("IndexBuilder: " + "lineCount=" + lineCount);\r
 310       }\r
 311       \r
 312       lineCount++;\r
 313       fileLocation = raf.getFilePointer();\r
 314     }\r
 315     raf.close();\r
 316     return root;\r
 317   }\r
 318 \r
 319 }\r