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