Реализовать поиск/найти следующий алгоритм

Ответ 1

Рассмотрим создание другой таблицы со структурой ниже

Table : index_table
columns : 
         index_id , word, occurrence, id(foreign key to your original table)

Сделайте один раз процесс индексирования, как показано ниже:

Итерации над каждой записью в исходной таблице разбивают текст на слова и для каждого поиска слов в новой таблице для существования, если нет, вставляют новую запись с вступлением, установленным как 1. Если существует вставка новой записи с вступлением = существующий появление +1

Как только вы сделали это, индексирование ваших выборок станет довольно простым. Например, для кота с 3-м совпадением будет

SELECT * 
FROM original_table o, index_table idx
WHERE idx.word = 'cat' 
  AND idx.occurrence = 3 
  AND o.id = idx.id

Ответ 2

Вам не нужна Lucene для этой работы. Кроме того, если у вас есть большое количество положительных совпадений, усилия по перекачке всех необходимых данных из вашей БД значительно превысят вычислительные затраты.

Здесь простое решение:

Индекс: нам требуются два свойства:

• эффективный доступ к словам для каждого id
• эффективно получить доступ ко всем идентификаторам в порядке возрастания.

следующим образом:

create index i_words on example_data (id, string_to_array(txt, ' '));

Запрос: найдите идентификатор, связанный с совпадением n th, со следующим запросом:

select id
from (
    select id, unnest(string_to_array(txt, ' ')) as word
    from example_data
) words
where word = :w     -- :w = 'cat'
offset :n - 1       -- :n = 3
limit 1;

Выполняется в 2 мс на 1 миллион строк.

Здесь полная настройка PostgreSQL, если вы предпочитаете попробовать себя, чем заверить мое слово:

drop table if exists example_data;
create table example_data (
    id integer primary key,
    txt text not null
);

insert into example_data
(select generate_series(1, 1000000, 3) as id, 'the cat is black' as txt
union all
select generate_series(2, 1000000, 3), 'a cat is a cat'
union all
select generate_series(3, 1000000, 3), 'a dog'
order by id);

commit;

drop index if exists i_words;
create index i_words on example_data (id, string_to_array(txt, ' '));

select id
from (
    select id, unnest(string_to_array(txt, ' ')) as word
    from example_data
) words
where word = 'cat'
offset 3 - 1
limit 1;

select 
    id, word
from (
    select id, unnest(string_to_array(txt, ' ')) as word
    from example_data
) words
where word = 'cat'
offset 3 - 1
limit 1;

Ответ 3

Обратите внимание, что я до сих пор не знаю, что именно означает "Выбрать третий матч для слова cat, то есть номер 2".

Возможные значения:

• вторая строка из результата, где 3-е слово - cat
• 3-я строка, где второе слово "cat"
• из всех строк, где "cat" появляется не менее 3 раз, возьмите вторую строку
• из всех строк, где "cat" появляется не менее 2 раз, возьмите третью строку

Если это 1 или 2, я думаю, что это можно сделать с приемлемой скоростью, используя индекс триграммы, чтобы уменьшить возможное количество совпадающих строк. Индекс триграммы (предоставленный модулем pg_trgm) позволяет Postgres использовать индекс при выполнении, например, like '%cat%'.

Предполагая, что только небольшое число строк удовлетворяет этому условию, результирующие строки затем могут быть разбиты на массивы и проверены на n-ое слово.

Что-то вроде этого:

with matching_rows as (
  select id, line, 
         row_number() over (order by id) as rn
  from the_table
  where line like '%cat%' -- this hopefully reduces the result to only very few rows
)
select *
from matching_rows 
where rn = 3 --<< "the third match for the word cat"
  and (string_to_array(line, ' '))[2] = 'cat' -- "the second word is "cat"

Обратите внимание, что индекс триграмм также имеет недостатки. Поддержание такого индекса намного дороже (= медленнее), чем поддержание регулярного индекса b-дерева. Поэтому, если ваша таблица сильно обновлена, это может быть не очень хорошее решение, но вам нужно проверить это для себя.

Кроме того, если условие `like '% cat%' действительно не уменьшает количество строк существенно, это, вероятно, тоже не будет выполнено.

Дополнительная информация о индексах триграмм:

• http://www.depesz.com/index.php/2011/02/19/waiting-for-9-1-faster-likeilike/
• http://www.postgresonline.com/journal/archives/212-PostgreSQL-9.1-Trigrams-teaching-LIKE-and-ILIKE-new-tricks.html

Другой вариант - отфильтровать "соответствующие" строки, используя полнотекстовый поиск Postgres, вместо обычного условия LIKE.

Ответ 4

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

Вы также можете написать задание в своем db, которое позволит вам создать обратную карту, string- > id. например:

rownum, id, text            
1       1   the cat is black
2       3   nice cat

к

key,    rownum, id
1_the   1       1
2_cat   1       1
3_is    1       1
4_black 1       1
1_nice  2       3
2_cat   2       3   

Если вы можете заказать по ID, вам не нужен rownum. Вы также должны называть столбец чем-то другим вместо rownum, я оставляю это для ясности

Теперь вы можете искать 1-й идентификатор, где слово cat является вторым словом, подобным этому, путем поиска

SELECT ID WHERE ROWNUM=1 AND key='3_CAT'

При создании индекса (id, key) или (key, id) ваши поиски должны быть довольно быстрыми.

Если вы можете поместить все эти данные в память, вы можете использовать простой Map<MyKey, Long> для поиска. MyKey будет более или менее Pair<Long,String> с правильными значениями equals и hashCode (и/или Comparable, если вы используете TreeMap).

Ответ 5

(Спасибо Даниэлю Гроскопфу за то, что я изначально неправильно истолковал вопрос.)

Этот запрос даст вам то, что вы хотите, только с SQL. Он получает текущее общее количество вхождений слова (например, "кошка" ) в текст, а затем возвращает первую строку, которая достигает порогового значения (например, 3).

SELECT id, text
  FROM (SELECT entries.*,
               SUM((SELECT COUNT(*)
                      FROM regexp_split_to_table(text, E'\\s+') AS words(word)
                     WHERE word = 'cat')) OVER (ORDER BY id) AS running_count
          FROM entries) AS entries_with_running_count
 WHERE running_count >= 3
 LIMIT 1

Смотрите в действии в SQL Fiddle

Ответ 6

Как бы вы справились с этим эффективным способом? Есть ли у вас трюк можете делать непосредственно в базе данных?

Вы не указываете, какие другие ограничения/требования вы можете иметь или что такое ваше определение

большое количество совпадений.

В качестве общего ответа я бы сказал, что выполнение строковых манипуляций в базе данных - это не эффективный подход.
Он слишком медленный и накладывает много работы на вашу БД, которая обычно является общим ресурсом.
ИМО вы должны делать это программно.
Способ сделать это может заключаться в том, чтобы сохранить метаданные в другой таблице, т.е. Индексы строк, которые содержат текст cat и где в предложении.
Вы можете запросить эту мета-таблицу, чтобы отобразить строки для запроса из вашей основной таблицы.
Эта дополнительная таблица более эффективна, чем поиск определенной таблицы, потому что запросы с LIKE в суффиксах не могут использовать индекс, и вы получите серийное сканирование, которое приведет к очень низкой производительности

Ответ 7

Решение для базы данных Postgres:

Добавьте новый столбец в таблицу:

alter table my_table add text_as_array text[];

Этот столбец будет содержать предложение, сочтенное словами:

"the cat is black" -> ["the","cat","is","black"]

Заполните этот столбец значениями из текущих записей:

update my_table set text_as_array = string_to_array(text,' ');

(и не забудьте установить значение string_to_array(text,' ') при вставке новых записей)

Создайте индекс gin:

create index my_table_text_as_array_index on text_as_array gin(text_as_array);
analyze my_table;

Тогда вам нужно просто выполнить быстрый запрос:

select *
from   my_table
where  text_as_array @> ARRAY['cat'] 
and    text_as_array[3] = 'cat' -- third word in sentence
order  by id
limit  1 
offset 2  -- second occurrence

В тестах, которые я сделал на своей машине, потребовалось 11 мс для поиска более ~ 2 400 000 записей.

Объясняю:

Limit  (cost=11252.08..11252.08 rows=1 width=104)
  ->  Sort  (cost=11252.07..11252.12 rows=19 width=104)
        Sort Key: id
        ->  Bitmap Heap Scan on my_table  (cost=48.21..11251.83 rows=19 width=104)
              Recheck Cond: (text_as_array @> '{cat}'::text[])
              Filter: (text_as_array[3] = 'cat'::text)
              ->  Bitmap Index Scan on my_table_text_as_array_index  (cost=0.00..48.20 rows=3761 width=0)
                    Index Cond: (text_as_array @> '{cat}'::text[])

Ответ 8

Решение "непосредственно в базе данных" кажется предпочтительным с точки зрения эффективности, поскольку большинство типов абстракции или загрузка/обработка в других местах могут повлечь дополнительные накладные расходы.

Если исходный текст можно массировать так, чтобы только пробелы отделяли слова (как упоминалось в комментариях, - возможно, путем предварительной обработки, чтобы заменить все не-алфавитные символов?), будет работать следующее (My) SQL-решение:

#############################################################
SET @searchWord = 'cat', # Search word: Must be lower case  #
    @n = 1,              # n where nth match is to be found #
#############################################################
    @matches = 0;        # Initialise local variable

SELECT s.*
FROM sentence s
WHERE id = 
(SELECT subq.id
 FROM
 (SELECT *,
         @matches AS prevMatches,
         (@matches := @matches + LENGTH(`text`) - LENGTH(
                      REPLACE(LOWER(`text`),
                              CONCAT(' ', @searchWord, ' '),
                              CONCAT(@searchWord, ' ')))
          + CASE WHEN LEFT(LOWER(`text`), 4) = CONCAT(@searchWord, ' ') THEN 1 ELSE 0 END
          + CASE WHEN RIGHT(LOWER(`text`), 4) = CONCAT(' ', @searchWord) THEN 1 ELSE 0 END)
     AS matches
  FROM sentence) AS subq
 WHERE subq.prevMatches < @n AND @n <= subq.matches);

Объяснение

Все экземпляры ' cat ' в каждой строке заменяются словом, которое на одну букву короче. Затем вычисляется разность в длине, чтобы узнать количество экземпляров. И, наконец, единственные возможности 'cat ' и ' cat', отображающие начало и конец строки, соответственно удовлетворяются. Сделав это, для каждой строки сохраняется общая сумма matches. Это связано с подзапросом, из которого n-го совпадения можно выбрать, найдя строку, в которой число кумулятивных чисел совпадений не больше n, но предыдущее значение меньше n.

Дальнейшие потенциальные улучшения

• Выше, конечно, можно было бы немного упростить, сделав нижестоящий текст исходного текста (что кажется разумным, если он предварительно обработан) и удаление всех вызовов на LOWER().
• Подзапрос вычисляет общее количество совпадений. Если вероятнее всего, что одни и те же условия поиска будут повторно использованы, возможно, возможно, можно кэшировать эти результаты в другой таблице и использовать триггеры для поддержания этого, когда записи обновляются, вставляются или удаляются, однако это значительно увеличило бы сложность и данные требования к хранению.

Ответ 9

Я бы поискал все строки с "cat", но ограничивал строки n. Это должно дать вам достаточно подмножество ваших данных, которое, как гарантируется, будет содержать строку, которую вы ищете. SQL будет выглядеть примерно так:

select id, text
  from your_table
 where text ~* 'cat'
  order by id
 limit 3 --nth time cat appears

Затем я бы выполнил ваше решение как функцию pl/pgsql, чтобы получить идентификатор, содержащий n-е вхождение вашего слова:

CREATE OR REPLACE FUNCTION your_schema.row_with_nth_occurrence(character varying, integer)
  RETURNS integer AS
$BODY$
Declare
  arg_search_word ALIAS FOR $1;
  arg_occurrence ALIAS FOR $2;

  v_sql         text;
  v_sql2        text;
  v_count       integer;
  v_count_total integer;
  v_record      your_table%ROWTYPE;

BEGIN

v_sql := 'select id, text
            from your_table
           where text ~* ' || arg_search_word || '
           order by id
           limit ' || arg_occurrence || ';';

v_count := 0;
v_count_total  := 0;
FOR v_record IN v_sql LOOP
  v_sql2 := 'SELECT count(*)
               FROM regexp_split_to_table('||v_record.text||', E'\\s+') a
              WHERE a = '|| arg_search_word ||';';
  EXECUTE v_sql2 INTO v_count;
  v_count_total := v_count_total + v_count;
  IF v_count_total >= arg_occurrence THEN
    RETURN v_record.id;
  END IF;
END LOOP;

RAISE EXCEPTION '% does not occur % times in the database.', arg_search_word, arg_occurrence;
END;

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

Ответ 10

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

Решение два: Используйте технологию Streamult ResultSet из драйвера JDBC; например.

     Statement select = connection.createStatement(ResultSet.TYPE_FORWARD_ONLY, ResultSet.CONCUR_READ_ONLY);
     select.setFetchSize(Integer.MIN_VALUE);
     ResultSet result = select.executeQuery(sql);

Как объяснено в http://dev.mysql.com/doc/connector-j/en/connector-j-reference-implementation-notes.html, прокрутите вниз до пункта Resultset. Это должно быть дружественным к памяти.

Теперь просто рассчитывайте на строки результатов до тех пор, пока они не будут удовлетворены и не закроют результат.

Ответ 11

У меня возникли проблемы с пониманием вашего заявления:

например: "Выберите третий матч для слова cat, то есть номер 2 запись". Результаты: вторая строка из результата, где 3-е слово - cat

Я предполагаю, что вы имеете в виду, что вы хотите искать записи, в которых третье слово текста является "cat", и из тех записей, которые вы хотите сделать второй.

Поскольку вы упомянули, что ваша проблема связана с одновременным доступом и скоростью, вам нужно как-то создать индекс, оптимизированный для вашего запроса. Вы можете использовать что-нибудь для этого, базу данных, lucene и т.д. Моим предложением было бы создать индекс в памяти. Просто подумайте об этом как о разогреве для вашего обслуживания, прежде чем он сможет начать подавать запрос.

В вашем случае вам нужна какая-то карта со словом и позицией слова в качестве ключа. Затем этот ключ будет отображаться в список номеров строк, соответствующих ключу. Поэтому, в конце концов, вам просто нужно дважды выполнить поиск, прежде всего, получить список номеров строк, где он совпадает, а затем номер строки, который вы хотите. Таким образом, производительность, в которой вам понадобится в конце, будет простой поиск по карте + поиск по списку массивов (константа).

Я привел очень простой пример ниже. Это непроверенный код, но он должен примерно дать вам идею.

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

// text entry from the DB
public class TextEntry {
    private int rowNb;
    private String text;
    // getters & setters
}

// your index class
public class Index {
    private Map<Key, List<Integer>> indexMap;
    // getters and setters

    public static class Key {
        private int wordPosition;
        private String word;
        // getters and setters
    }
}

// your searcher class
public class Searcher {

    private static Index index = null;
    private static List<TextEntry> allTextEntries = null;


    public static init() {
        // init all data with some synchronization check

        // synchronization check whether index has been built

        allTextEntries.forEach(entry -> {
          // split the words, and build the index based on the word position and the word
          String[] words = entry.split(" ");
          for (int i = 0; i < words.length; i++) {
              Index.Key key = new Index.Key(i + 1, words[i]);
              int rowNumber = entry.getRowNb();
              // if the key is already there, just add the row number if it not the last one
              if (indexMap.contains(key)) {
                  List entryMatch = indexMap.get(key);
                  if (entryMatch.get(entryMatch.size() - 1) !== rowNumber) {
                    entryMatch.add(rowNumber);
                  }
              } else {
                  // if key is not there, add a new one
                  List entryMatch = new ArrayList<Integer>()
                  entryMatch.add(rowNumber);
                  indexMap.put(key, entryMatch);
              }
          }
        });
    }

    public static TextEntry search(String word, int wordPosition, int resultNb) {
        // call init if not yet called, do some check

        int rowNb = index.getIndexMap().get(new Index.Key(word, wordPosition)).get(resultNb - 1);
        return allTextEntries.get(rowNb);
    }

}

Ответ 12

В mysql Нам нужна одна функция, где мы можем подсчитать количество вхождений данной подстроки в поле.

Создать функцию (эта функция будет подсчитывать наличие подстроки в данном столбце)

 CREATE FUNCTION substrCount(
         x varchar(255), delim varchar(12)) returns int
    return (length(x)-length(REPLACE(x,delim, '')))/length(delim);

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

Я разбиваю эту проблему на 3 части, и мы можем сделать это с помощью хранимой процедуры.

• Выберите все строки, содержащие строку "cat" (или любой другой вход). Это должно выбрать максимум n строк (n = no из вложений), поэтому мы будем использовать предел в нашем запросе.
• С курсором перебирайте согласованные строки во время roop.
• Приращение вхождения соответствует каждой строке в переменной count и выходите после того, как найдено количество совпадений (должно быть возможно найти совпадение в пределах от 1 до n циклов)

создать хранимую процедуру. Предполагая правильный индекс, это должно быть быстрым.

DELIMITER $$

CREATE PROCEDURE find_match(INOUT string_to_match varchar(100),
 INOUT occurence_count INTEGER,OUT match_field varchar(100))
BEGIN

 DECLARE v_count INTEGER DEFAULT 0;
 DECLARE v_text varchar(100) DEFAULT "";

 -- declare cursor and select by the order you want.
 DEClARE matcher_cursor CURSOR FOR 
 SELECT textField FROM myTable 
        where textField like string_to_match 
              order by id 
              LIMIT 0, occurence_count;

 -- declare NOT FOUND handler
 DECLARE CONTINUE HANDLER 
        FOR NOT FOUND SET v_finished = -1;

 OPEN matcher_cursor;

 get_matching_occurence: LOOP

 FETCH matcher_cursor INTO v_text;

 IF v_count = -1 THEN 
 LEAVE get_matching_occurence;
 END IF;

 -- use substring count function 
 v_count:= v_count + substrCount(v_text,string_to_match));

-- if count is equal to greater than occurenece that means matching row is found.
IF (v_count>= occurence_count) THEN

 SET match_field = v_text;
 v_count:=-1;

END IF;

 END LOOP get_matching_occurence;

 CLOSE _

END$$

DELIMITER ;

Ответ 13

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

select t.*
from (select t.*, sum(cnt) over (order by id) as cumecnt
      from (select t.*,
                   (length(' ' || str || ' ') - length(replace(' ' || str || ' '), ' cat ', '')) / length(' cat ') as cnt
            from t
           ) t
      where num > 0
     ) t
where cumecnt >= 3 and cumecnt - cnt <= 3;

Вы просто замените "3" и "cat" соответствующими строками.

Этот метод требует сканирования строк несколько раз в каждой строке (один раз для каждой длины и один раз для замены). Я предполагаю, что это быстрее, чем различные операции с массивом, регулярные выражения или текст. Если у вас есть более сложные определения того, что такое слово, вам, вероятно, придется использовать регулярное выражение replace:

Выполнение работы в базе данных обычно является большой победой. Однако, если вы ищете 6-й матч из одного миллиона строк, возможно, быстрее будет считывать значения из подзапроса и выполнять накопление в приложении. Я не думаю, что есть способ сократить время вычисления базы данных, чтобы остановиться только на "шестой" строке.

Ответ 14

Я тестировал это на таблице с 1,2 миллионами строк и возвращает данные менее чем за секунду. Я использую функцию split (которая является модифицированной формой функции сплиттера Jeff Modem) здесь: 'http://sqlperformance.com/2012/08/t-sql-queries/splitting-strings-follow-up'.`

-- Step 1. Create table
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
SET ANSI_PADDING ON
GO
CREATE TABLE [dbo].[Sentence](
    [id] [int] IDENTITY(1,1) NOT NULL,
    [Text][varchar](250) NULL,
CONSTRAINT [PK_Sentence] PRIMARY KEY CLUSTERED 
    (
    [id] ASC
    )WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
    ) ON [PRIMARY]

GO
SET ANSI_PADDING OFF
GO

Шаг 2. Создайте функцию разделения

CREATE FUNCTION [dbo].[SplitSentence]
(
   @CSVString NVARCHAR(MAX),
   @Delimiter NVARCHAR(255)
)
RETURNS TABLE
WITH SCHEMABINDING AS
RETURN
  WITH E1(N)        AS ( SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 
                     UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 
                     UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1),
   E2(N)        AS (SELECT 1 FROM E1 a, E1 b),
   cteTally(N)  AS (SELECT 0 
                    UNION ALL 
                    SELECT TOP (DATALENGTH(ISNULL(@CSVString,1))) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) FROM E2),
   cteStart(N1) AS (SELECT t.N+1 
                    FROM cteTally t
                     WHERE (SUBSTRING(@CSVString,t.N,1) = @Delimiter OR t.N = 0))
  SELECT Word = SUBSTRING(@CSVString, s.N1, ISNULL(NULLIF(CHARINDEX(@Delimiter,@CSVString,s.N1),0)-s.N1,50))
  FROM cteStart s;

Шаг 3. Создайте sql script, чтобы вернуть требуемые данные

DECLARE @n int = 3
DECLARE @Word varchar(50) = 'cat'
;WITH myData AS 
(SELECT TOP (@n)
    id
    ,[Text]
    ,sp.word
    ,ROW_NUMBER() OVER (ORDER BY Id) RowNo
FROM 
    Sentence 
CROSS APPLY (SELECT * FROM SplitSentence(Sentence.[Text],' ')) sp
WHERE Word = @Word)
SELECT 
    * 
FROM 
    myData 
WHERE 
    RowNo = @n

Предположения:

 1. The sentence has a max length of 250 characters. If needed this can be modified in the create table statement.
 2. The sentence will not have more than a 100 words. If more than 100 words are needed, the split function will have to be modified.
 3. Any word in the sentence has a max length of 50 characters.

Демо-версия SQL Fiddle здесь: http://sqlfiddle.com/#!3/0a1d0/1

Notes: 
I am aware that the original requirement is for MySQL/pgsql, 
but I have limited knowledge of these and therefore my solution has been created/tested in MSSQL.