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