Форум программистов, компьютерный форум, киберфорум
C# .NET
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.93/15: Рейтинг темы: голосов - 15, средняя оценка - 4.93
 Аватар для ndrnesterov
4 / 4 / 3
Регистрация: 28.11.2017
Сообщений: 107

Нечеткий поиск по столбцу

13.01.2020, 10:40. Показов 3022. Ответов 11

Студворк — интернет-сервис помощи студентам
Добрый день.

Есть столбец в DataTable ["LINE"] с адресами типа ("Ростовская область, г. Ростов-на-Дону, ул. Красноармейская, д 93/4").
Таких строк в столбце больше миллиона...

На форме есть comboBox, в котором пользователь будет вбивать, например, "ростов красноарм". comboBox будет раскрываться и показывать возможные варианты адреса.

И вот я застрял на нечетком поиске подстроки в строке... Я пробовал алгоритм Левенштейна, но для такого кол-ва строк он очень долгий...

Кликните здесь для просмотра всего текста
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int LevenshteinDistance(string string1, string string2)
{
    int diff;
    int[,] m = new int[string1.Length + 1, string2.Length + 1];
 
    for (int i = 0; i <= string1.Length; i++) { m[i, 0] = i; }
    for (int j = 0; j <= string2.Length; j++) { m[0, j] = j; }
 
    for (int i = 1; i <= string1.Length; i++)
    {
        for (int j = 1; j <= string2.Length; j++)
        {
            diff = (string1[i - 1] == string2[j - 1]) ? 0 : 1;
 
            m[i, j] = Math.Min(Math.Min(m[i - 1, j] + 1,
                                     m[i, j - 1] + 1),
                                     m[i - 1, j - 1] + diff);
        }
    }
    return m[string1.Length, string2.Length];
}


Очень быстро и круто работает поиск через Contains, но там нет нечеткого поиска..

Кликните здесь для просмотра всего текста
C#
1
2
3
4
5
6
7
for (int i = 0; i < join_table.Rows.Count; i++)
            {
                if (join_table.Rows[i]["LINE"].ToString().Contains(comboBox1.Text))
                    comboBox1.Items.Add(join_table.Rows[i]["LINE"].ToString());            
            }
 
            comboBox1.DroppedDown = true;


Может кто-то сталкивался с такой задачей. Как ее можно решить?

На счет dadata и т.д. - не вариант. Нужно, чтобы поиск работал автономно, без интернета. Все делается по скачанной базе ФИАС.
0
Лучшие ответы (1)
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
13.01.2020, 10:40
Ответы с готовыми решениями:

Нечеткий поиск в базе данных
Всем доброго времени суток. Помогите создать нечеткий (по буквам) поиск данных, которые выведены в datagridview. Заранее спасибо!

Нечеткий поиск
Здравствуйте, мне нужно сделать нечеткий поиск(по левенштейну). Типа вводим в текстбоксе слово(фамилию например) и сравниваем с таблицей....

Как реализовать нечеткий поиск, используя алгоритм Левенштейна?
Необходимо сделать так,чтобы при вводе текста появлялись схожие слова. Сравниваемые слова находятся в массиве.

11
163 / 138 / 35
Регистрация: 25.11.2015
Сообщений: 910
13.01.2020, 12:05
В contains проверяй не все выражение целиком, а по словам.
т.е. "ростов красноарм" это два слова для поиска.

А тут уже как тебе интересно будет. Можешь второе слово искать в результатах первого, можешь результаты в AddRange скидывать...
0
 Аватар для ndrnesterov
4 / 4 / 3
Регистрация: 28.11.2017
Сообщений: 107
13.01.2020, 12:18  [ТС]
Цитата Сообщение от yurickas Посмотреть сообщение
В contains проверяй не все выражение целиком, а по словам.
Думал об этом... Предположим я из всей строки уберу знаки препинания с помощью regex и разделю строку на несколько строк с помощью split. Дальше я вижу такой сценарий:
Я создаю лист и загоняю туда все индексы подходящих строк от первого слова. Далее создаю лист и загоняю туда индексы подходящих строк от второго слова. И т.д. Далее я нахожу повторяющиеся индексы и вывожу строки по этим индексам... Это займет очень много времени...

Как можно это реализовать? Подскажи идею)
0
163 / 138 / 35
Регистрация: 25.11.2015
Сообщений: 910
13.01.2020, 13:37
Зачем много времени. Один запрос, если работаешь из EF. В linq собираешь запрос из where и потом одной транзакцией вытягиваешь.
Чем больше слов, тем больше промежуточных запросов и тем дольше он будет исполняться, поэтому я бы еще ввел лимит выдачи, скажем там 50 записей.

И зачем для разделения строки использовать regex?
C#
1
2
3
 var str = "подо проа";
 
 var arr = str.Split(new Char[] {' ', ',', ':'}).ToList();
1
 Аватар для ndrnesterov
4 / 4 / 3
Регистрация: 28.11.2017
Сообщений: 107
13.01.2020, 13:58  [ТС]
Цитата Сообщение от yurickas Посмотреть сообщение
В linq собираешь запрос из where и потом одной транзакцией вытягиваешь.
Подскажи, как это можно сделать? В linq я только начал разбираться...

В моем случае есть DataTable join_table, у которого есть столбец LINE. И пользователь вводит текст в comboBox1.Text.
Помоги с написанием linq запроса)

Я пока реализовал вот так:
Кликните здесь для просмотра всего текста
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
byte fl = 0;
string s = comboBox1.Text;
 
            foreach (DataRow row in join_table.Rows)
            {
                if (row["LINE"].ToString().ToUpper().Contains(s.ToUpper()))
                {
                    comboBox1.Items.Add(row["LINE"].ToString());
                    fl++;
                }
 
                if (fl > 9) break;
            }
0
880 / 559 / 291
Регистрация: 21.11.2012
Сообщений: 1,554
13.01.2020, 17:06
если поиск происходит по целым словам:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public static void Main(string[] args)
        {
            var rnd = new Random();
            var enter = "consetetur takimata";
            
            string s = "Lorem ipsum dolor sit amet, consetetur sadipscing elitr, " +
                "sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, " +
                "sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. " +
                "Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet.Lorem " +
                "ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut " +
                "labore et dolore magna aliquyam erat, sed diam voluptua.At vero eos et accusam et justo duo " +
                "dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet.";
 
            var arr = s.Split(new char[] { '.', ' ', ',' }, StringSplitOptions.RemoveEmptyEntries);
 
            var list = new List<string>();
 
            for(int i = 0; i < 2000000; i++)
            {
                var str = "";
                
                for(int j = 0; j < rnd.Next(1, 20); j++)
                {
                    str += arr[rnd.Next(arr.Count())] + " ";
                }
                list.Add(str.TrimEnd());
            }
 
            var search = list.Where(x => x.Split().ContainsAll(enter.Split()));
 
            Console.ReadKey();
        }
 
public static class ExtensionsList
    {
        public static bool ContainsAll<T>(this IEnumerable<T> list, params T[] items)
        {
            foreach (var item in items)
            {
                if (!list.Contains(item))
                    return false;
            }
 
            return true;
        }
    }
1
 Аватар для ndrnesterov
4 / 4 / 3
Регистрация: 28.11.2017
Сообщений: 107
13.01.2020, 17:24  [ТС]
Цитата Сообщение от hamin Посмотреть сообщение
если поиск происходит по целым строкам:
Интересно) Сейчас буду тестировать! А пока я сделал вот так и у меня почти хорошо получилось:
Кликните здесь для просмотра всего текста
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
            byte fl = 0;
 
            foreach (DataRow row in join_table.Rows)
            {
                if (Search(row["LINE"].ToString(),s.Split(' ')))
                {
                    listBox1.Items.Add(row["LINE"].ToString());
                    fl++;
                }
                if (fl > 9) break;
            }
 
bool Search(string str, string[] words)
        {
            foreach (var word in words)
            {
                if (str.IndexOf(word, StringComparison.OrdinalIgnoreCase) == -1)
                {
                    return false;
                }
            }
 
            return true;
        }


Надеюсь ваш пример будет работать стабильнее)

А ещё мне интересно, что у вас написано в тексте?) Я пытался перевести через переводчик, но что-то вообще непонятное получилось... Это латынь?)
0
880 / 559 / 291
Регистрация: 21.11.2012
Сообщений: 1,554
13.01.2020, 17:32
ndrnesterov,

это текст - утка, бессмысленный набор слов, используется часто при разработках дизайна как текст для заполнения какой-нибудь области
1
Эксперт .NET
 Аватар для Usaga
14145 / 9374 / 1350
Регистрация: 21.01.2016
Сообщений: 35,299
14.01.2020, 06:41
Лучший ответ Сообщение было отмечено ndrnesterov как решение

Решение

Цитата Сообщение от ndrnesterov Посмотреть сообщение
Очень быстро и круто работает поиск через Contains, но там нет нечеткого поиска..
Очень быстро и круто работает только полнотекстовый индекс. Но это отдельная структура данных, которую нужно построить по вашим данным и которая занимает место.

Если вы поиск производите именно в СУБД, то там такой индекс уже поддерживается (кроме Firebird, там нужно отдельную тулзу прикручивать). Его нужно просто включить для нужных колонок. Ну и обращаться к нему нужно определённым образом в запросе.

Если с вами что-то не то (полнолуние или ударились сильно) и вы весь миллион строк храните в оперативке, то вы можете использовать всё тот же Contains. С той лишь разницей, что желательно ввод пользователя разбивать на отдельные слова ("ростов" и "красноарм") и искать их отдельно объединяя условие через логическое И:

SQL
1
SELECT [список_колонок] FROM [таблица] WHERE Line LIKE '%ростов%' AND Line LIKE '%красноарм%'
Или в EF (который обозвали словом "Linq" выше):
C#
1
2
3
var results = context.TableName
      .Where(x => x.Line.Contains("ростов") && x.Line.Contains("красноарм"))
      .ToList();
Технология доступа к данным тут совершенно роли не играет и идея одна и та же: предикат описывающий наличие несколько слов в одной строке.

Цитата Сообщение от ndrnesterov Посмотреть сообщение
Таких строк в столбце больше миллиона...
Но я надеюсь, что это всё хранится в СУБД, где есть полнотекстовый поиск. Такой поиск СУЩЕСТВЕННО быстрее, чем Contains.
1
163 / 138 / 35
Регистрация: 25.11.2015
Сообщений: 910
14.01.2020, 07:42
Цитата Сообщение от Usaga Посмотреть сообщение
Или в EF (который обозвали словом "Linq" выше):
не, не в том плане, что я EF обозвал, а в том плане, что всю конструкцию для поиска можно через линк собрать и вытащить одним запросом.

Цитата Сообщение от Usaga Посмотреть сообщение
Но я надеюсь, что это всё хранится в СУБД, где есть полнотекстовый поиск. Такой поиск СУЩЕСТВЕННО быстрее, чем Contains.
и вот тут да, Contains далеко не самый быстрый способ. Только как мне кажется полноценного полнотекстового поиска в EF так и не реализовали? Остается ручная правка миграции и прямой SQL-запрос или хранимая процедура?
0
Эксперт .NET
 Аватар для Usaga
14145 / 9374 / 1350
Регистрация: 21.01.2016
Сообщений: 35,299
14.01.2020, 07:52
Цитата Сообщение от yurickas Посмотреть сообщение
Только как мне кажется полноценного полнотекстового поиска в EF так и не реализовали?
Так это же фича СУБД, а не EF'а. Другое дело, что запрос обращения к такому индексу (SELECT ... FROM ... WHERE ... MATCH ...) из EF не сделать, а значит действительно или SQL-запрос или вызов процедуры.
0
 Аватар для ndrnesterov
4 / 4 / 3
Регистрация: 28.11.2017
Сообщений: 107
15.01.2020, 10:46  [ТС]
Цитата Сообщение от Usaga Посмотреть сообщение
Если вы поиск производите именно в СУБД, то там такой индекс уже поддерживается
Спасибо) Твой ответ помог. Я все же решил все эти таблицы записать в базу данных и туда делать запросы. Это очень быстро)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
15.01.2020, 10:46
Помогаю со студенческими работами здесь

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

Поиск по столбцу dataGridView
Здравствуйте! Такой вопрос. Есть кнопка, при нажатие на него добавляется в первом столбце dataGridView сегодняшняя дата. Теперь хочу...

Поиск по столбцу в datagridview
Здравствуйте. В общем, есть у меня форма, где я из txt-файла вывожу инфу в datagridview. Потом я на второй форме, которую вызываю через...

Поиск по одному столбцу в DataGridView
как искать только по одному столбцу? пожалуйста помогите, ищу всю ночь не могу найти решение

DataGridView. Поиск по определенному столбцу
Делаю прогу по взаимодействию с БД. Хочу сделать поиск в опредеоенном столбце (где совподает хоть 1-но слово).Но возникла проблема . Вот...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Новые блоги и статьи
Символьное дифференцирование
igorrr37 13.02.2026
/ * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image
8Observer8 10.02.2026
Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .
Установка Qt-версии Lazarus IDE в Debian Trixie Xfce
volvo 10.02.2026
В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru