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