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