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