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