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