Инвертированный поиск: Фразы на документ

Question

У меня есть база данных, полная фраз (80-100 символов), а также несколько длинных документов (50-100Kb), и мне нужен ранжированный список фраз для данного документа; а не обычный вывод поисковой системы, список документов для данной фразы.

Я использовал полнотекстовое индексирование MYSQL раньше и смотрел в lucene, но никогда не использовал его. Они кажутся ориентированными на сравнение короткого (поискового термина) с длинным (документом).

Как вы бы описали его?

Answer 1

Я сделал что-то похожее с базой данных из названий Википедии и сумел спуститься до нескольких сотен миллисекунд за каждый документ ~ 50 КБ. Это было все еще недостаточно быстро для моих нужд, но, возможно, это может сработать для вас.

В основном идея заключалась в том, чтобы как можно больше работать с хешами и выполнять только строковые сравнения на возможных совпадениях, которые довольно редки.

Сначала вы берете свою базу данных и конвертируете ее в массив хешей. Если у вас есть миллиарды фраз, это может быть не для вас. Когда вы вычисляете хэш, обязательно передавайте фразы через токенизатор, который удалит знаки препинания и пробелы. Эта часть должна быть выполнена только один раз.

Затем вы идете по документу с тем же токенизатором, сохраняя список запусков последних 1,2, .., n токенов, хешированных.На каждой итерации вы выполняете двоичный поиск хешей, которые у вас есть против базы хешей.

Когда вы найдете совпадение, вы выполняете фактическое сравнение строк, чтобы узнать, нашли ли вы совпадение.

Вот код, чтобы дать вам вкус подогреть я имею в виду, жесткий этот пример не на самом деле сделать сравнение строк:

  HashSet<Long> foundHashes = new HashSet<Long>(); 

      LinkedList<String> words = new LinkedList<String>(); 
      for(int i=0; i<params.maxPhrase; i++) words.addLast(""); 

      StandardTokenizer st = new StandardTokenizer(new StringReader(docText)); 
      Token t = new Token(); 
      while(st.next(t) != null) { 
       String token = new String(t.termBuffer(), 0, t.termLength()); 
       words.addLast(token); 
       words.removeFirst(); 

       for(int len=params.minPhrase; len<params.maxPhrase; len++) { 
        String term = Utils.join(new ArrayList<String>(words.subList(params.maxPhrase-len,params.maxPhrase)), " "); 

        long hash = Utils.longHash(term); 

        if(params.lexicon.isTermHash(hash)) { 
         foundHashes.add(hash); 
        } 
       } 
      } 

      for(long hash : foundHashes) { 
       if(count.containsKey(hash)) { 
        count.put(hash, count.get(hash) + 1); 
       } else { 
        count.put(hash, 1); 
       } 
      } 

Answer 2

Было бы слишком медленно превращать каждую фразу в регулярное выражение и запускать каждый из них в документе, подсчитывая количество вхождений?

Если это не сработает, возможно, вы можете комбинировать все фразы в одном огромном регулярном выражении (используя |) и скомпилировать его. Затем запустите это огромное регулярное выражение, начиная с каждого символа документа. Подсчитайте количество совпадений при прохождении символов.

Answer 3

Какая информация содержит большое количество фраз? Я предполагаю, что он очень большой.

Я хотел бы сделать следующее:

1. Индекс фразы по одному из слов в нем. Вы можете выбрать наименьшее общее слово в каждой фразе. Вы можете сделать поиск лучше, предположив, что это слово, по крайней мере, например. 5 символов, и добавьте слово до 5 символов, если оно короче. Заполнение может быть пробелом после слова, за которым следует последующее слово, для уменьшения совпадений или какого-либо символа по умолчанию (например, «XX»), если слово встречается в конце фразы.

2. Пройдите через свой документ, преобразуя каждое слово (общее из них можно отбросить) к ключу, дополняя, если необходимо, извлечение фраз.

3. Извлечь соответствующие фразы по этим ключевым словам.

4. Используйте текстовый поиск в памяти, чтобы найти количество вхождений каждой из полученных фраз.

5. Я предполагаю, что фразы не могут пересекать границу предложения. В этом случае вы можете прочитать каждое предложение документа в подстроке массива и использовать функцию подстроки для поиска по каждому предложению для каждой из фраз и счетчиков, сохраняя текущую сумму для каждой фразы.

Answer 4

Возможно чтение Peter Turney on keyphrase extraction даст вам некоторые идеи. В целом, его подход имеет некоторое сходство с тем, что предположил itsadok.