src/com/hughes/android/dictionary/engine/Index.java

   1 // Copyright 2011 Google Inc. All Rights Reserved.
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License");
   4 // you may not use this file except in compliance with the License.
   5 // You may obtain a copy of the License at
   6 //
   7 //     http://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS,
  11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 // See the License for the specific language governing permissions and
  13 // limitations under the License.
  14
  15 /**
  16  *
  17  */
  18 package com.hughes.android.dictionary.engine;
  19
  20 import com.hughes.android.dictionary.DictionaryInfo;
  21 import com.hughes.android.dictionary.DictionaryInfo.IndexInfo;
  22 import com.hughes.android.dictionary.engine.RowBase.RowKey;
  23 import com.hughes.util.CachingList;
  24 import com.hughes.util.TransformingList;
  25 import com.hughes.util.raf.RAFList;
  26 import com.hughes.util.raf.RAFSerializable;
  27 import com.hughes.util.raf.RAFSerializer;
  28 import com.hughes.util.raf.SerializableSerializer;
  29 import com.hughes.util.raf.UniformRAFList;
  30 import com.ibm.icu.text.Collator;
  31 import com.ibm.icu.text.Transliterator;
  32
  33 import java.io.IOException;
  34 import java.io.PrintStream;
  35 import java.io.RandomAccessFile;
  36 import java.util.ArrayList;
  37 import java.util.Collection;
  38 import java.util.Collections;
  39 import java.util.EnumMap;
  40 import java.util.HashSet;
  41 import java.util.LinkedHashMap;
  42 import java.util.LinkedHashSet;
  43 import java.util.List;
  44 import java.util.Map;
  45 import java.util.Set;
  46 import java.util.concurrent.atomic.AtomicBoolean;
  47 import java.util.regex.Pattern;
  48
  49 public final class Index implements RAFSerializable<Index> {
  50
  51   static final int CACHE_SIZE = 5000;
  52
  53   public final Dictionary dict;
  54
  55   public final String shortName;  // Typically the ISO code for the language.
  56   public final String longName;
  57
  58   // persisted: tells how the entries are sorted.
  59   public final Language sortLanguage;
  60   final String normalizerRules;
  61
  62   // Built from the two above.
  63   private Transliterator normalizer;
  64
  65   // persisted
  66   public final List<IndexEntry> sortedIndexEntries;
  67
  68   // persisted.
  69   public final Set<String> stoplist;
  70
  71   // One big list!
  72   // Various sub-types.
  73   // persisted
  74   public final List<RowBase> rows;
  75   public final boolean swapPairEntries;
  76
  77   // Version 2:
  78   int mainTokenCount = -1;
  79
  80   // --------------------------------------------------------------------------
  81
  82   public Index(final Dictionary dict, final String shortName, final String longName, final Language sortLanguage, final String normalizerRules, final boolean swapPairEntries, final Set<String> stoplist) {
  83     this.dict = dict;
  84     this.shortName = shortName;
  85     this.longName = longName;
  86     this.sortLanguage = sortLanguage;
  87     this.normalizerRules = normalizerRules;
  88     this.swapPairEntries = swapPairEntries;
  89     sortedIndexEntries = new ArrayList<IndexEntry>();
  90     this.stoplist = stoplist;
  91     rows = new ArrayList<RowBase>();
  92
  93     normalizer = null;
  94   }
  95
  96   /**
  97    * Deferred initialization because it can be slow.
  98    */
  99   public synchronized Transliterator normalizer() {
 100     if (normalizer == null) {
 101       normalizer = Transliterator.createFromRules("", normalizerRules, Transliterator.FORWARD);
 102     }
 103     return normalizer;
 104   }
 105
 106   /**
 107    * Note that using this comparator probably involves doing too many text normalizations.
 108    */
 109   public NormalizeComparator getSortComparator() {
 110     return new NormalizeComparator(normalizer(), sortLanguage.getCollator());
 111   }
 112
 113   public Index(final Dictionary dict, final RandomAccessFile raf) throws IOException {
 114     this.dict = dict;
 115     shortName = raf.readUTF();
 116     longName = raf.readUTF();
 117     final String languageCode = raf.readUTF();
 118     sortLanguage = Language.lookup(languageCode);
 119     normalizerRules = raf.readUTF();
 120     swapPairEntries = raf.readBoolean();
 121     if (sortLanguage == null) {
 122       throw new IOException("Unsupported language: " + languageCode);
 123     }
 124     if (dict.dictFileVersion >= 2) {
 125       mainTokenCount = raf.readInt();
 126     }
 127     sortedIndexEntries = CachingList.create(RAFList.create(raf, indexEntrySerializer, raf.getFilePointer()), CACHE_SIZE);
 128     if (dict.dictFileVersion >= 4) {
 129       stoplist = new SerializableSerializer<Set<String>>().read(raf);
 130     } else {
 131       stoplist = Collections.emptySet();
 132     }
 133     rows = CachingList.create(UniformRAFList.create(raf, new RowBase.Serializer(this), raf.getFilePointer()), CACHE_SIZE);
 134   }
 135
 136   @Override
 137   public void write(final RandomAccessFile raf) throws IOException {
 138     raf.writeUTF(shortName);
 139     raf.writeUTF(longName);
 140     raf.writeUTF(sortLanguage.getIsoCode());
 141     raf.writeUTF(normalizerRules);
 142     raf.writeBoolean(swapPairEntries);
 143     if (dict.dictFileVersion >= 2) {
 144       raf.writeInt(mainTokenCount);
 145     }
 146     RAFList.write(raf, sortedIndexEntries, indexEntrySerializer);
 147     new SerializableSerializer<Set<String>>().write(raf, stoplist);
 148     UniformRAFList.write(raf, (Collection<RowBase>) rows, new RowBase.Serializer(this), 5 /* bytes per entry */);
 149   }
 150
 151   public void print(final PrintStream out) {
 152     for (final RowBase row : rows) {
 153       row.print(out);
 154     }
 155   }
 156
 157   private final RAFSerializer<IndexEntry> indexEntrySerializer = new RAFSerializer<IndexEntry> () {
 158       @Override
 159       public IndexEntry read(RandomAccessFile raf) throws IOException {
 160         return new IndexEntry(Index.this, raf);
 161       }
 162       @Override
 163       public void write(RandomAccessFile raf, IndexEntry t) throws IOException {
 164         t.write(raf);
 165       }};
 166
 167
 168   public static final class IndexEntry implements RAFSerializable<Index.IndexEntry> {
 169     private final Index index;
 170     public final String token;
 171     private final String normalizedToken;
 172     public final int startRow;
 173     public final int numRows;  // doesn't count the token row!
 174     public final List<HtmlEntry> htmlEntries;
 175
 176
 177     public IndexEntry(final Index index, final String token, final String normalizedToken, final int startRow, final int numRows) {
 178       this.index = index;
 179       assert token.equals(token.trim());
 180       assert token.length() > 0;
 181       this.token = token;
 182       this.normalizedToken = normalizedToken;
 183       this.startRow = startRow;
 184       this.numRows = numRows;
 185       this.htmlEntries = new ArrayList<HtmlEntry>();
 186     }
 187
 188     public IndexEntry(final Index index, final RandomAccessFile raf) throws IOException {
 189       this.index = index;
 190       token = raf.readUTF();
 191       startRow = raf.readInt();
 192       numRows = raf.readInt();
 193       final boolean hasNormalizedForm = raf.readBoolean();
 194       normalizedToken = hasNormalizedForm ? raf.readUTF() : token;
 195       if (index.dict.dictFileVersion >= 6) {
 196         this.htmlEntries = CachingList.create(RAFList.create(raf, index.dict.htmlEntryIndexSerializer, raf.getFilePointer()), 1);
 197       } else {
 198         this.htmlEntries = Collections.emptyList();
 199       }
 200     }
 201
 202     public void write(RandomAccessFile raf) throws IOException {
 203       raf.writeUTF(token);
 204       raf.writeInt(startRow);
 205       raf.writeInt(numRows);
 206       final boolean hasNormalizedForm = !token.equals(normalizedToken);
 207       raf.writeBoolean(hasNormalizedForm);
 208       if (hasNormalizedForm) {
 209         raf.writeUTF(normalizedToken);
 210       }
 211       RAFList.write(raf, htmlEntries, index.dict.htmlEntryIndexSerializer);
 212     }
 213
 214     public String toString() {
 215       return String.format("%s@%d(%d)", token, startRow, numRows);
 216     }
 217
 218     public String normalizedToken() {
 219       return normalizedToken;
 220     }
 221   }
 222
 223   static final TransformingList.Transformer<IndexEntry, String> INDEX_ENTRY_TO_TOKEN = new TransformingList.Transformer<IndexEntry, String>() {
 224     @Override
 225     public String transform(IndexEntry t1) {
 226       return t1.token;
 227     }
 228   };
 229
 230   public IndexEntry findExact(final String exactToken) {
 231     final int result = Collections.binarySearch(TransformingList.create(sortedIndexEntries, INDEX_ENTRY_TO_TOKEN), exactToken, getSortComparator());
 232     if (result >= 0) {
 233       return sortedIndexEntries.get(result);
 234     }
 235     return null;
 236   }
 237
 238   public IndexEntry findInsertionPoint(String token, final AtomicBoolean interrupted) {
 239     final int index = findInsertionPointIndex(token, interrupted);
 240     return index != -1 ? sortedIndexEntries.get(index) : null;
 241   }
 242
 243   public int findInsertionPointIndex(String token, final AtomicBoolean interrupted) {
 244     token = normalizeToken(token);
 245
 246     int start = 0;
 247     int end = sortedIndexEntries.size();
 248
 249     final Collator sortCollator = sortLanguage.getCollator();
 250     while (start < end) {
 251       final int mid = (start + end) / 2;
 252       if (interrupted.get()) {
 253         return -1;
 254       }
 255       final IndexEntry midEntry = sortedIndexEntries.get(mid);
 256
 257       final int comp = sortCollator.compare(token, midEntry.normalizedToken());
 258       if (comp == 0) {
 259         final int result = windBackCase(token, mid, interrupted);
 260         return result;
 261       } else if (comp < 0) {
 262         System.out.println("Upper bound: " + midEntry + ", norm=" + midEntry.normalizedToken() + ", mid=" + mid);
 263         end = mid;
 264       } else {
 265         System.out.println("Lower bound: " + midEntry + ", norm=" + midEntry.normalizedToken() + ", mid=" + mid);
 266         start = mid + 1;
 267       }
 268     }
 269
 270     // If we search for a substring of a string that's in there, return that.
 271     int result = Math.min(start, sortedIndexEntries.size() - 1);
 272     result = windBackCase(sortedIndexEntries.get(result).normalizedToken(), result, interrupted);
 273     return result;
 274   }
 275
 276   private final int windBackCase(final String token, int result, final AtomicBoolean interrupted) {
 277     while (result > 0 && sortedIndexEntries.get(result - 1).normalizedToken().equals(token)) {
 278       --result;
 279       if (interrupted.get()) {
 280         return result;
 281       }
 282     }
 283     return result;
 284   }
 285
 286   public IndexInfo getIndexInfo() {
 287     return new DictionaryInfo.IndexInfo(shortName, sortedIndexEntries.size(), mainTokenCount);
 288   }
 289
 290   private static final int MAX_SEARCH_ROWS = 1000;
 291
 292   private final Map<String,Integer> prefixToNumRows = new LinkedHashMap<String, Integer>();
 293   private synchronized final int getUpperBoundOnRowsStartingWith(final String normalizedPrefix, final int maxRows, final AtomicBoolean interrupted) {
 294     final Integer numRows = prefixToNumRows.get(normalizedPrefix);
 295     if (numRows != null) {
 296       return numRows;
 297     }
 298     final int insertionPointIndex = findInsertionPointIndex(normalizedPrefix, interrupted);
 299
 300     int rowCount = 0;
 301     for (int index = insertionPointIndex; index < sortedIndexEntries.size(); ++index) {
 302       if (interrupted.get()) { return -1; }
 303       final IndexEntry indexEntry = sortedIndexEntries.get(index);
 304       if (!indexEntry.normalizedToken.startsWith(normalizedPrefix)) {
 305         break;
 306       }
 307       rowCount += indexEntry.numRows;
 308       if (rowCount > maxRows) {
 309         System.out.println("Giving up, too many words with prefix: " + normalizedPrefix);
 310         break;
 311       }
 312     }
 313     prefixToNumRows.put(normalizedPrefix, numRows);
 314     return rowCount;
 315   }
 316
 317
 318   public final List<RowBase> multiWordSearch(final List<String> searchTokens, final AtomicBoolean interrupted) {
 319     final long startMills = System.currentTimeMillis();
 320     final List<RowBase> result = new ArrayList<RowBase>();
 321
 322     final Set<String> normalizedNonStoplist = new LinkedHashSet<String>();
 323
 324     String bestPrefix = null;
 325     int leastRows = Integer.MAX_VALUE;
 326     final StringBuilder regex = new StringBuilder();
 327     for (int i = 0; i < searchTokens.size(); ++i) {
 328       if (interrupted.get()) { return null; }
 329       final String searchToken = searchTokens.get(i);
 330       final String normalized = normalizeToken(searchTokens.get(i));
 331       // Normalize them all.
 332       searchTokens.set(i, normalized);
 333
 334       if (!stoplist.contains(searchToken)) {
 335         if (normalizedNonStoplist.add(normalized)) {
 336           final int numRows = getUpperBoundOnRowsStartingWith(normalized, MAX_SEARCH_ROWS, interrupted);
 337           if (numRows != -1 && numRows < leastRows) {
 338             if (numRows == 0) {
 339               // We really are done here.
 340               return Collections.emptyList();
 341             }
 342             leastRows = numRows;
 343             bestPrefix = normalized;
 344           }
 345         }
 346       }
 347
 348       if (regex.length() > 0) {
 349         regex.append("[\\s]*");
 350       }
 351       regex.append(Pattern.quote(normalized));
 352     }
 353     final Pattern pattern = Pattern.compile(regex.toString());
 354
 355     if (bestPrefix == null) {
 356       bestPrefix = searchTokens.get(0);
 357       System.out.println("Everything was in the stoplist!");
 358     }
 359     System.out.println("Searching using prefix: " + bestPrefix + ", leastRows=" + leastRows + ", searchTokens=" + searchTokens);
 360
 361     // Place to store the things that match.
 362     final Map<RowMatchType,List<RowBase>> matches = new EnumMap<RowMatchType, List<RowBase>>(RowMatchType.class);
 363     for (final RowMatchType rowMatchType : RowMatchType.values()) {
 364       if (rowMatchType != RowMatchType.NO_MATCH) {
 365         matches.put(rowMatchType, new ArrayList<RowBase>());
 366       }
 367     }
 368
 369     int matchCount = 0;
 370     final Set<RowKey> cachedRowKeys = new HashSet<RowBase.RowKey>();
 371
 372 //    for (final String searchToken : searchTokens) {
 373     final String searchToken = bestPrefix;
 374
 375     final int insertionPointIndex = findInsertionPointIndex(searchToken, interrupted);
 376
 377     for (int index = insertionPointIndex; index < sortedIndexEntries.size() && matchCount < MAX_SEARCH_ROWS; ++index) {
 378         if (interrupted.get()) { return null; }
 379         final IndexEntry indexEntry = sortedIndexEntries.get(index);
 380         if (!indexEntry.normalizedToken.startsWith(searchToken)) {
 381           break;
 382         }
 383
 384 //        System.out.println("Searching indexEntry: " + indexEntry.token);
 385
 386         // Extra +1 to skip token row.
 387         for (int rowIndex = indexEntry.startRow + 1; rowIndex < indexEntry.startRow + 1 + indexEntry.numRows && rowIndex < rows.size(); ++rowIndex) {
 388           if (interrupted.get()) { return null; }
 389           final RowBase row = rows.get(rowIndex);
 390           final RowBase.RowKey rowKey = row.getRowKey();
 391           if (cachedRowKeys.contains(rowKey)) {
 392             continue;
 393           }
 394           cachedRowKeys.add(rowKey);
 395           final RowMatchType matchType = row.matches(searchTokens, pattern, normalizer(), swapPairEntries);
 396           if (matchType != RowMatchType.NO_MATCH) {
 397             matches.get(matchType).add(row);
 398             ++matchCount;
 399           }
 400         }
 401       }
 402 //    }  // searchTokens
 403
 404     // Sort them into a reasonable order.
 405     final RowBase.LengthComparator lengthComparator = new RowBase.LengthComparator(swapPairEntries);
 406     for (final Collection<RowBase> rows : matches.values()) {
 407       final List<RowBase> ordered = new ArrayList<RowBase>(rows);
 408       Collections.sort(ordered, lengthComparator);
 409       result.addAll(ordered);
 410     }
 411
 412     //System.out.println("searchDuration: " + (System.currentTimeMillis() - startMills));
 413     return result;
 414   }
 415
 416   private String normalizeToken(final String searchToken) {
 417     if (TransliteratorManager.init(null)) {
 418       final Transliterator normalizer = normalizer();
 419       return normalizer.transliterate(searchToken);
 420     } else {
 421       // Do our best since the Transliterators aren't up yet.
 422       return searchToken.toLowerCase();
 423     }
 424   }
 425
 426 }