Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Составить все возможные предложения из набора слов  [new]
Galyamov Rinat
Member

Откуда:
Сообщений: 658
Конечная цель: По строке поиска найти все улицы (по названиям), в которых есть вхождения всех слов из этой строки. При этом порядок слов в строке поиска должен быть не важен. Так же слово в строке поиска может быть не полным (первые буквы)

Пример: Есть улица "Сергея Лазо". Мы должны ее найти независимо от того как вводился текст в строке поиска "С лазо", "Лазо С", "Сергея Лазо", "Сер лаз", "Лаз Сер" и т.п.

Для этого я разделяю строку поиска на отельные слова.


Теперь задача из этих слов составить все возможные варианты предложений.
В случае со строкой из двух слов будет всего два варианта. "С лазо" - это "%С%лазо%" и "%лазо%С%"

В случае трех - уже шесть вариантов.
И т.д.

В случае двух слов задача решается простым джоином:
declare @tbl_Seached_Text table (id int identity (1,1), Seached_Text varchar(max))

insert into @tbl_Seached_Text (Seached_Text) values ('Сергея'), ('Лазо')

select '%'+A.Seached_Text+'%'+B.Seached_Text+'%' as Seached_Text
	from @tbl_Seached_Text A inner join @tbl_Seached_Text B on A.id <> B.id



А как быть в общем случае, когда кол-во слов заранее не известно?
4 апр 13, 06:31    [14133557]     Ответить | Цитировать Сообщить модератору
 Re: Составить все возможные предложения из набора слов  [new]
aleks2
Guest
Galyamov Rinat
А как быть в общем случае, когда кол-во слов заранее не известно?

1. Убиться ап стенку.
2. Алгоритм у вас несложный.
2.1. Разбить на слова и сунуть их в таблицу.
2.2. Отстригая от каждого слова по одной букве сзаду сгенерировать новые слова и дописать их в таблицу.
2.3. Сцепить новые слова обратно во всех порядках (cross join) и сунуть в временную таблицу.
2.4. Сделать join с этой временной таблицей.

Чо тут сложного?
4 апр 13, 07:38    [14133605]     Ответить | Цитировать Сообщить модератору
 Re: Составить все возможные предложения из набора слов  [new]
Galyamov Rinat
Member

Откуда:
Сообщений: 658
aleks2,

Совет очень хороший. Особенно п.1 Надеюсь вы им и воспользуетесь.

Относительно п.2
По п.2.1 и 2.4 вопросов у меня нет.
п.2.2 Я, честно говоря, не понял. Если вы имеете в в иду способ разделения на слова, то у меня это уже реализовано. И, соответственно, вопросов по данному пункту нет.

А вот с п.2.3 как раз таки и есть вопрос. Каким образом можно сделать cross join, чтобы при наличии трех слов вернулся набор данных из шести строк с различным положением слов в предложении?


PS Поднял полнотекстовый индекс. Прикручиваю его...
4 апр 13, 08:06    [14133641]     Ответить | Цитировать Сообщить модератору
 Re: Составить все возможные предложения из набора слов  [new]
Galyamov Rinat
Member

Откуда:
Сообщений: 658
Galyamov Rinat
aleks2,
А вот с п.2.3 как раз таки и есть вопрос. Каким образом можно сделать cross join, чтобы при наличии трех слов вернулся набор данных из шести строк с различным положением слов в предложении?


А если 4 слова? А 5?
А в общем случае?


Первоначальный вопрос как раз и заключался в том, что вы "описали" в п.2.3
4 апр 13, 08:16    [14133657]     Ответить | Цитировать Сообщить модератору
 Re: Составить все возможные предложения из набора слов  [new]
invm
Member

Откуда: Москва
Сообщений: 9406
Galyamov Rinat,

1. Хотите чтоб работало быстро -- используйте FTS.
2. Хотите свой собственный велосипед -- поисковая строка и значения в столбце бьются на слова, далее банальное реляционное деление. И не нужно никаких перестановок слов.
4 апр 13, 09:06    [14133768]     Ответить | Цитировать Сообщить модератору
 Re: Составить все возможные предложения из набора слов  [new]
Cygapb-007
Member

Откуда:
Сообщений: 1677
велисапед:)
declare @tbl_Seached_Text table (id int identity (1,1), Seached_Text varchar(max))
insert @tbl_Seached_Text (Seached_Text) values ('Сергея Лазо улица'),('улица первого мая'),('ленинский проспект'),('энтузиастическая')

declare @search varchar(256)='л'

;with words as (
   select 1 id, '% '+case i when 0 then s else left(s,i-1) end+'% ' word, case i when 0 then '' else SUBSTRING(s,i+1,256) end rest
      from(values(@search))s(s)
	   cross apply (select CHARINDEX(' ',s.s)i) a
   union all
   select id+1,'% '+case i when 0 then w.rest else left(w.rest,i-1) end+'% ', case i when 0 then '' else SUBSTRING(w.rest,i+1,256)end
      from words w
      cross apply (select CHARINDEX(' ',w.rest)i) a
      where w.rest>''
	)
--select * from words

select top (1) with ties t.id,t.Seached_Text,COUNT(*)qty
from @tbl_Seached_Text t
cross apply (select 
   len(Seached_Text)-len(REPLACE(Seached_Text,' ','')) sw,
   len(@search)-len(REPLACE(@search,' ','')) nw
   ) ca
join words w on ' '+t.Seached_Text+' ' like w.word
--where sw=nw
group by t.id,t.Seached_Text,nw
--having COUNT(*)=nw+1
order by qty desc
4 апр 13, 09:21    [14133812]     Ответить | Цитировать Сообщить модератору
 Re: Составить все возможные предложения из набора слов  [new]
Galyamov Rinat
Member

Откуда:
Сообщений: 658
invm,
Что есть "банальное реляционное деление" ?
4 апр 13, 09:51    [14133928]     Ответить | Цитировать Сообщить модератору
 Re: Составить все возможные предложения из набора слов  [new]
Galyamov Rinat
Member

Откуда:
Сообщений: 658
Cygapb-007,

Реализация деления на слова оригинальная.
Но вот поиск по "Все слова должны иметь вхождение" не работает.

Работает "Хоть одно слово имеет вхождение".

Например меняем
declare @search varchar(256)='л'

на
declare @search varchar(256)='л ХХХХХХХ'

Все равно выдаст Лазо.


Ну и как я понимаю FTS все равно будет быстрее?
4 апр 13, 09:54    [14133943]     Ответить | Цитировать Сообщить модератору
 Re: Составить все возможные предложения из набора слов  [new]
Cygapb-007
Member

Откуда:
Сообщений: 1677
все слова должны быть - раскоментировать where и having
4 апр 13, 09:56    [14133953]     Ответить | Цитировать Сообщить модератору
 Re: Составить все возможные предложения из набора слов  [new]
Galyamov Rinat
Member

Откуда:
Сообщений: 658
Cygapb-007,

Вроде как where не нужен.
С having`ом работает ожидаемо, но уже прикрутил FTS :).
4 апр 13, 10:34    [14134180]     Ответить | Цитировать Сообщить модератору
 Re: Составить все возможные предложения из набора слов  [new]
iap
Member

Откуда: Москва
Сообщений: 47001
Galyamov Rinat
invm,
Что есть "банальное реляционное деление" ?
Наберите в поиске по этому форуму "реляционное деление".
4 апр 13, 10:38    [14134210]     Ответить | Цитировать Сообщить модератору
 Re: Составить все возможные предложения из набора слов  [new]
iap
Member

Откуда: Москва
Сообщений: 47001
iap
Galyamov Rinat
invm,
Что есть "банальное реляционное деление" ?
Наберите в поиске по этому форуму "реляционное деление".
Можно и погуглить, но здесь уже давались очень хорошие ссылки - ищите.
4 апр 13, 10:40    [14134224]     Ответить | Цитировать Сообщить модератору
 Re: Составить все возможные предложения из набора слов  [new]
aleks2
Guest
Galyamov Rinat
А вот с п.2.3 как раз таки и есть вопрос. Каким образом можно сделать cross join, чтобы при наличии трех слов вернулся набор данных из шести строк с различным положением слов в предложении?


Дык выполнить cross join два (три, али скока нада ) раз?

ЗЫ. Все таки стенка для вас более гуманный выход.
4 апр 13, 11:58    [14134826]     Ответить | Цитировать Сообщить модератору
 Re: Составить все возможные предложения из набора слов  [new]
Jaffar
Member

Откуда:
Сообщений: 633
нужно сделать так:

1. разбить строку поиска на части по пробелам или еще каким знакам.
2.Напихать это все в таблицу.(табл. перем)
3.сгенерить динамический запрос
типа

selcet *
from t_Street t with(nolock)
where
t.StreetName like '%'+кусок1+'%'
and t.StreetName like '%'+кусок2+'%'
and t.StreetName like '%'+кусок2+'%'
..........
and t.StreetName like '%'+кусокN+'%'


вот и все. и никаких cte и т.п.
4 апр 13, 14:00    [14135699]     Ответить | Цитировать Сообщить модератору
 Re: Составить все возможные предложения из набора слов  [new]
Jaffar
Member

Откуда:
Сообщений: 633
declare @__TEMP table(String varchar(255) unique)

insert @__TEMP(String) 
          select 'АС'
union all select 'Б'
union all select 'Е'

declare @SQL varchar(max)
select @SQL = ''

select top 100500 @SQL = @SQL + 'and s.Caption like ''%'+t.String+'%'' '+char(13)+char(10)
from @__TEMP t
order by len(String) desc

select @SQL = 
'select *
from tref_Street s with(nolock)
where 
   '+substring(@SQL, 4, 100500)+
'order by s.Caption asc'

print @SQL
exec(@SQL)
4 апр 13, 14:12    [14135779]     Ответить | Цитировать Сообщить модератору
 Re: Составить все возможные предложения из набора слов  [new]
iap
Member

Откуда: Москва
Сообщений: 47001
Jaffar
нужно сделать так:

1. разбить строку поиска на части по пробелам или еще каким знакам.
2.Напихать это все в таблицу.(табл. перем)
3.сгенерить динамический запрос
типа

selcet *
from t_Street t with(nolock)
where
t.StreetName like '%'+кусок1+'%'
and t.StreetName like '%'+кусок2+'%'
and t.StreetName like '%'+кусок2+'%'
..........
and t.StreetName like '%'+кусокN+'%'


вот и все. и никаких cte и т.п.
Если после парсинга в таблицу напиханы только слова, то зачем динамический запрос, LIKE и т.д.?
Просто "=" или "IN" или "EXISTS" не сгодятся?
4 апр 13, 14:13    [14135780]     Ответить | Цитировать Сообщить модератору
 Re: Составить все возможные предложения из набора слов  [new]
anna.serg
Member

Откуда: smolensk-spb
Сообщений: 122
Jaffar, но тогда нужен некоторый счетчик для like-ов
по количеству введенных кусков слов.
иначе в ответ на запрос 'Сер Лаз'
будет выбрана не только 'Сергея Лазо', но и
'Сергиевская'..

но поддержу идею aleks2 с несколькими cross join
по количеству введененных кусков слов
4 апр 13, 15:20    [14136190]     Ответить | Цитировать Сообщить модератору
 Re: Составить все возможные предложения из набора слов  [new]
Хмммм
Guest
anna.serg
Jaffar, но тогда нужен некоторый счетчик для like-ов
по количеству введенных кусков слов.
иначе в ответ на запрос 'Сер Лаз'
будет выбрана не только 'Сергея Лазо', но и
'Сергиевская'..

но поддержу идею aleks2 с несколькими cross join
по количеству введененных кусков слов

А вы не путаете and и or?
4 апр 13, 21:50    [14137935]     Ответить | Цитировать Сообщить модератору
 Re: Составить все возможные предложения из набора слов  [new]
Dima T
Member

Откуда:
Сообщений: 15028
Galyamov Rinat
В случае со строкой из двух слов будет всего два варианта. "С лазо" - это "%С%лазо%" и "%лазо%С%"

разбей на два и более условий и объедини через AND
where Table.cText like '%С%' and Table.cText like '%лазо%'

это не быстро будет, но на небольших таблицах думаю сойдет.
если известно что это начало слова, то есть смысл сделать отдельное поле по которому искать и туда писать "причесанное" значение. При причесывании убрать лишние символы и поставить пробел перед каждым словом
"ул.Сергея Лазо" => " ул Сергея Лазо"
тогда можно так будет делать
where Table.cText like '% С%' and Table.cText like '% лазо%'


быстрый вариант: сделать отдельную таблицу слов Word(nWordId, cWord) и таблицу связи слов с текстом WordText(nWordId, nTextId)
дальше так
select nTextId
   from (select distinct nTextId from WordText where nWordId in (select nWordId from Word where cWord like 'c%')
              union all
           select distinct nTextId from WordText where nWordId in (select nWordId from Word where cWord like 'лазо%')) A
   group by nTextId
   having count(*) = 2

С синтаксисом возможно напутал немного, смысл такой: выбираем ID текстов где встречается каждое слово, затем оставляем те ID в которых встречаются все слова (count(*) = 2).
5 апр 13, 07:43    [14138437]     Ответить | Цитировать Сообщить модератору
 Re: Составить все возможные предложения из набора слов  [new]
Maxx
Member [скрыт]

Откуда:
Сообщений: 24290
В свое время DeColores предложил вот такое решение
5 апр 13, 10:32    [14138832]     Ответить | Цитировать Сообщить модератору
 Re: Составить все возможные предложения из набора слов  [new]
Galyamov Rinat
Member

Откуда:
Сообщений: 658
anna.serg
но поддержу идею aleks2 с несколькими cross join
по количеству введененных кусков слов


Пример запроса с cross join можете привести в поддержку? :-)

PS Честно говоря не очень нравится идея динамического запроса...
5 апр 13, 16:00    [14141229]     Ответить | Цитировать Сообщить модератору
 Re: Составить все возможные предложения из набора слов  [new]
Galyamov Rinat
Member

Откуда:
Сообщений: 658
Maxx,

С озвученной задачей наиболее правильно и удачно справляется FTS.

Надо было всего - лишь разобраться с ним. Преимущества очевидны:
1 - индексированный поиск.
2 - искомая строка готовится простыми replace(...) без необходимости разбора на слова и сохранения этих слов в таблице (для последующего подзапроса или джоина (вот только не кроссового, как некоторые советую :-) )
3 - FTS со своим NEAR(...) вернет более логически верный результат, чем подзапросы или предикаты, типа "like", "=", "in" Напрмер, если запросить строку "Лаз Серг Серг Серг", то все запросы с
like "%Лаз%" or like "%Серг%" or like "%Серг%" or like "%Серг%"
вернут "Сергея Лазо" (хотя это уже не очень логично).


Из всех "лисапедов", логичным и наиболее оригинальным выглядит решение Cygapb-007. Хотя и его решение не лишено указанного в п.3 недостатка.


Вывод - в данной ситуации FTS рулит. Всем спасибо.
5 апр 13, 16:13    [14141317]     Ответить | Цитировать Сообщить модератору
 Re: Составить все возможные предложения из набора слов  [new]
Jaffar
Member

Откуда:
Сообщений: 633
Galyamov Rinat,

Ну если вы хотите вводить "Сер Сер Сер" и получать только ул. Сергея Сергевича Сергеева - то тогда вот так:

declare @__TEMP table(String varchar(255) not NULL, CNT int)

insert @__TEMP(String, CNT) 
select Part, count(1)
from (    select 'АС' Part
union all select 'Б'
union all select 'Е'
union all select 'Е'
union all select 'Е') t
group by Part

select * from @__TEMP

declare @SQL varchar(max)
select @SQL = ''

select top 100500 @SQL = @SQL + 'and s.Caption like '''+t2.String+'%'' '+char(13)+char(10)
from @__TEMP t
cross apply(select replicate('%'+t.String, t.CNT) String) t2
order by len(t2.String) desc

select @SQL = 
'select *
from tref_Street s with(nolock)
where 
   '+substring(@SQL, 4, 100500)+
'order by s.Caption asc'

print @SQL
exec(@SQL)
17 апр 13, 06:54    [14190143]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить