Автор Тема: Търсене и съвпадения  (Прочетена 18426 пъти)

console

  • Напреднали
  • *****
  • Публикации: 243
    • Профил
    • WWW
Търсене и съвпадения
« -: Feb 06, 2019, 16:33 »
Здравейте,

Казуса е следния :

Има над милион записа в таблица. Тези записи са на различни продукти. Примерно Телефон Nokia, Слушаки LG и т.н.

Имаме още една таблица с продукти които са предоставени от клиенти примерно.

Това което трябва да стане е да мачна едната таблица със другата на базата на имената на продуктите.

Проблема е че външните са описвани както им е било кеф на хората. Са разбира се проблема е как да стане мачването по-бързо.Наясно съм че това на 100% неможе да стане. Базата данни изобщо няма да ми свърши бързо тази работа тя просто си работи бавно за такива неща и трябва да напиша нещо което да го смели по-бързо.

Основното ми питане е какъв език е най-добре да се изоолзва за да минава бързо процеса. Пробвах с php и не ме изкефи изобщо защото за около 560 продукта подадени от клиенти цялото мачване през стотиците записи от таблицата с продукти мина за около 20 мин. То са вярно и лаптопа дето тествах не е много мощен но все пак 20 минути ми се сториха адски много за такъв тип операция.
« Последна редакция: Feb 06, 2019, 16:37 от console »
Активен

“Ever tried. Ever failed. No matter. Try again. Fail again. Fail Better.”

makeme

  • Напреднали
  • *****
  • Публикации: 895
  • Distribution: Many
  • Window Manager: KDE
    • Профил
Re: Търсене и съвпадения
« Отговор #1 -: Feb 06, 2019, 16:40 »
Здравейте,

Казуса е следния :

Има над милион записа в таблица. Тези записи са на различни продукти. Примерно Телефон Nokia, Слушаки LG и т.н.

Имаме още една таблица с продукти които са предоставени от клиенти примерно.

Това което трябва да стане е да мачна едната таблица със другата на базата на имената на продуктите.

Проблема е че външните са описвани както им е било кеф на хората. Са разбира се проблема е как да стане мачването по-бързо.Наясно съм че това на 100% неможе да стане. Базата данни изобщо няма да ми свърши бързо тази работа тя просто си работи бавно за такива неща и трябва да напиша нещо което да го смели по-бързо.

Основното ми питане е какъв език е най-добре да се изоолзва за да минава бързо процеса. Пробвах с php и не ме изкефи изобщо защото за около 560 продукта подадени от клиенти цялото мачване през стотиците записи от таблицата с продукти мина за около 20 мин. То са вярно и лаптопа дето тествах не е много мощен но все пак 20 минути ми се сториха адски много за такъв тип операция.
За език не знам, но ако сложиш базата на машина със SSD (колкото и мизерна да е тя) ти гарантирам осезаемо по малко време (/5 или /10)
Активен

Distributions:  UbuntuMate; Kubuntu; CentOS; Kali; Raspberry Pi OS ...

jet

  • Напреднали
  • *****
  • Публикации: 3472
  • Distribution: debian
  • Window Manager: kde
    • Профил
Re: Търсене и съвпадения
« Отговор #2 -: Feb 06, 2019, 21:29 »
Не става ясно каква е тази база данни, но дано не е SQLite.
Ако e MySQL едва ли Php е нещото дето я бави. Разгледай заявките които правиш дали не връщат много записи въртяни в цикъл.
Активен

..⢀⣴⠾⠻⢶⣦⠀
  ⣾⠁⢠⠒⠀⣿⡁
  ⢿⡄⠘⠷⠚⠋
  ⠈⠳⣄⠀⠀⠀⠀  Debian, the universal operating system.

spec1a

  • Напреднали
  • *****
  • Публикации: 3852
    • Профил
Re: Търсене и съвпадения
« Отговор #3 -: Feb 06, 2019, 21:57 »
   Не си написал каква е базата данни.
   Аз бих заложил на С++ , да,по-сложно е,изисква повече писане на код,
но е номер 1 по бързодействие при езиците от високо ниво.
Активен

4096bits

  • Напреднали
  • *****
  • Публикации: 6152
    • Профил
Re: Търсене и съвпадения
« Отговор #4 -: Feb 06, 2019, 22:58 »
Хм! Не, че съм се занимавал с бази данни, обаче който и език да се използва, търсенето няма ли да се направи на практика от самата база данни? Програмния език просто има библиотека, която е интерфейс към нея, за да може да си говорят... Или нещо бъркам?
Активен

As they say in Mexico, "Dasvidaniya!" Down there, that's two vidaniyas.

remotexx

  • Напреднали
  • *****
  • Публикации: 3210
    • Профил
Re: Търсене и съвпадения
« Отговор #5 -: Feb 07, 2019, 02:28 »
SQL, освен ако не е NoSQL

А между другото каква е СУБД дето се ползва?

И какъв алгоритъм се ползва за намиране на съвпадения?

https://www.kdnuggets.com/2019/01/comparison-text-distance-metrics.html

и конкретен пример
https://en.m.wikipedia.org/wiki/Levenshtein_distance
« Последна редакция: Feb 07, 2019, 02:34 от remotexx »
Активен

console

  • Напреднали
  • *****
  • Публикации: 243
    • Профил
    • WWW
Re: Търсене и съвпадения
« Отговор #6 -: Feb 07, 2019, 07:54 »
Базата данни е postgre но в случая аз не я ползвам освен да запиша резултатите като при теста дори и връзка с базата не съм правил просто гледах за колко време ще мине скрипта. Аз съм взел всички продукти от базата и съм ги бутнал в едно csv както и тези които са подадени от клиенти. Това което направих с php беше просто да заредя в паметта и двата файла и да ги обхождам при търсене на съвпадения.Алгоритъма които ползвах http://php.net/similar-text понеже тази фунция е build in би трябвало да сработи по-бързо отколкото алгоритъм писан от мене но ми се струва че не алгоритъма забавя положението.

Мисля че bash може да здъвче проблема доста по-бързо и сега ще гледам с grep какви са ми възможностите и вариантите.
Активен

“Ever tried. Ever failed. No matter. Try again. Fail again. Fail Better.”

4096bits

  • Напреднали
  • *****
  • Публикации: 6152
    • Профил
Re: Търсене и съвпадения
« Отговор #7 -: Feb 07, 2019, 09:24 »
Три-четири реда примерни реда от csv-то?
Впрочем, защо не правиш заявка директо към базата данни?
Активен

As they say in Mexico, "Dasvidaniya!" Down there, that's two vidaniyas.

console

  • Напреднали
  • *****
  • Публикации: 243
    • Профил
    • WWW
Re: Търсене и съвпадения
« Отговор #8 -: Feb 07, 2019, 10:30 »
Пример от csv-to с продуктите

iPad with WiFi + Cellular  32GB  Space Gray
Apple iPhone 7 Smart Battery Case
MacBook Pro 15 Retina Display с Touch Bar  Space Gray 2.8GHz

Това което подава клиента :

MacBook Pro 15 Retina Display
iPad 6 with WiFi + Cellular  128GB
iPad Pro 12.9 WiFi + Cellular 256GB  Silver

Цялата игра е да може да се намери добро съвпадение и да се опита да познае това което подава клиента към кой продукт от базата съответсва. Това няма как да стане на 100% със всички това е ясно но въпроса е поне процеса да минава бързо с мачването.

Не правя връзка с базата понеже забавя процеса, по бързо ще зареди csv отколкото да направя SELECT * FROM products.

Впечатляващо е как grep работи. Файла с продуктите от базата е над 300МБ и grep намира съвпадения за по малко от секунда. Явно с него и някъв regex би трябвало да свърши перфектна работа.
Активен

“Ever tried. Ever failed. No matter. Try again. Fail again. Fail Better.”

Naka

  • Напреднали
  • *****
  • Публикации: 3395
    • Профил
Re: Търсене и съвпадения
« Отговор #9 -: Feb 07, 2019, 11:21 »
Ако искаш изключително бързо, ама за 1-2 сек.  :o това се прави с 'reverse index', 'inverted index' или поне така го наричаха. Така работят търсачкие (Гого например.). Обаче за реализация е досто трудоемко.

правил съм такова нещо: (и още го правя :()

Идеята е следната. Прави се една таблица, в която са описани всички (уникални) думи които се срещат в базата.
това са мойте таблици (само за идеята):

 
Код:
mysql> describe word_index;
+-------+-----------------------+------+-----+---------+----------------+
| Field | Type                  | Null | Key | Default | Extra          |
+-------+-----------------------+------+-----+---------+----------------+
| id    | mediumint(8) unsigned | NO   | PRI | NULL    | auto_increment |
| word  | varchar(32)           | NO   | MUL |         |                |
+-------+-----------------------+------+-----+---------+----------------+
2 rows in set (0.00 sec)


и се прави още една таблица в която пък се описват всяка уникална id=word_id дума в точно кой продукт се среща. (offerta_id е при мене, при теб е продукт_id).  (weight и su_weight са си мои теглови коефициенти, вместо тях може да е нещо друго или изобщо да ги няма)
Код:
mysql> describe search_index;
+------------+-----------------------+------+-----+---------+-------+
| Field      | Type                  | Null | Key | Default | Extra |
+------------+-----------------------+------+-----+---------+-------+
| word_id    | mediumint(8) unsigned | NO   | MUL | 0       |       |
| offerta_id | int(10) unsigned      | NO   | MUL | 0       |       |
| weight     | tinyint(3) unsigned   | NO   |     | 0       |       |
| su_weight  | tinyint(3) unsigned   | NO   |     | 0       |       |
+------------+-----------------------+------+-----+---------+-------+
4 rows in set (0.00 sec)
при търсене, това което подава клиента пак се разделя на думи , виждат се кои са уникалните думи  word_index и по тях и по втората таблица се виждат в кой продукт се срещат.

Обаче куерито за самото търсене е много заплетено (Но пък е много бързо). Според зависи от нуждите. То например може да брои броят съвпаденията на думите в стринга, може да изчислява някакъв тегловен коефициент и т.н. Според зависи.


Това е идеята....Обаче не впускай да го правиш, че е занимавка за години.
Недостатък е че при всяка промяна на текста в някой продукт, трябва наново да се изграждат, двете таблици. Аз съм си направил един скрипт, дето се пуска всяка нощ. Недостък е че през това време, промените не се отразяват на търсенето, и клиента ще вижда старите резултати. Е те този скрипт е тежкият и върти поне 30 мин.

Досега не ми е стигнало времето да го направя, таблиците да се обновявят динамично.
Друг недостатък е че това е 100% съвпадение на отделните думи. Не е levenshtein() или soundex() .... Но мисля че може така с този 'reverse index' да се пригоди и по този начин.


––––––––––
ПС: А колкото до  regex. preg_* на PHP-то работят много бързо. Може да е даже по-бързо и от grep-a.



« Последна редакция: Feb 07, 2019, 12:04 от Naka »
Активен

Perl - the only language that looks the same before and after encryption.

makeme

  • Напреднали
  • *****
  • Публикации: 895
  • Distribution: Many
  • Window Manager: KDE
    • Профил
Re: Търсене и съвпадения
« Отговор #10 -: Feb 07, 2019, 11:49 »
Впечатляващо е как grep работи. Файла с продуктите от базата е над 300МБ и grep намира съвпадения за по малко от секунда. Явно с него и някъв regex би трябвало да свърши перфектна работа.
Ако работиш с текстови файлове (тхт, цсв или дори дъмп) грепа е твоето нещо. Идеята е че тогава отпада това което ти предложих за ССД-то. 1вия греп може да ти мине по-бавничко, но след това всички файлове отиват в кеш буфера (рамта) и греповете минават даже за много под секунда.

ПП: При postgre не знам как е, но това е идеята на innodb при mysql. Вдигаш буфера и се получава същото. Просто хардовете са ужасни за много текст на едно място :)
« Последна редакция: Feb 07, 2019, 11:53 от makeme »
Активен

Distributions:  UbuntuMate; Kubuntu; CentOS; Kali; Raspberry Pi OS ...

remotexx

  • Напреднали
  • *****
  • Публикации: 3210
    • Профил
Re: Търсене и съвпадения
« Отговор #11 -: Feb 07, 2019, 16:50 »
Solr
Активен

Odido

  • Напреднали
  • *****
  • Публикации: 627
  • Distribution: Arch Linux
  • Window Manager: Gnome
    • Профил
Re: Търсене и съвпадения
« Отговор #12 -: Feb 07, 2019, 19:36 »
Solr
Оха,1400 страници гайд.Ама изглежда доста интересно.
Активен

"Congratulations, you broke the Internet
Look at what you did! Are you happy now?"

4096bits

  • Напреднали
  • *****
  • Публикации: 6152
    • Профил
Re: Търсене и съвпадения
« Отговор #13 -: Feb 07, 2019, 21:12 »
За това ли става въпрос?
Има и една библиотека за Питон - asyncpg - използваща asyncio, но не ми се е налагало да я ползвам. На хартия изглежда добре. Ако се включи и Nuitka в играта, може да стане наистина интересно.

https://magic.io/blog/asyncpg-1m-rows-from-postgres-to-python/
Активен

As they say in Mexico, "Dasvidaniya!" Down there, that's two vidaniyas.

remotexx

  • Напреднали
  • *****
  • Публикации: 3210
    • Профил
Re: Търсене и съвпадения
« Отговор #14 -: Feb 09, 2019, 02:25 »
Да, точно за това става въпрос. Който иска може да се пробва напр. И с това което предлагат стандартните СУБД

https://dev.mysql.com/doc/refman/8.0/en/fulltext-natural-language.html

Но да внимава, щото имат и капани и подводни камъни
https://hackernoon.com/dont-waste-your-time-with-mysql-full-text-search-61f644a54dfa


Докато, Solr е създаден с една единствена цел, и се справя доста добре - веднъж изграден индекса, всичко става за секунди

П.П. Другия (по лесен) вариант е да пробваш с некой десктоп търсачка... Първо и даваш да ти индексира само папката с ,CSV файл четата и после търсиш...
Само че те Google desktop search го убиха още време оно, beagle и той... Не се сещам сега какво се ползва...

П.П.П. явно сега е на мода те т'ва
https://en.m.wikipedia.org/wiki/Recoll
« Последна редакция: Feb 09, 2019, 02:34 от remotexx »
Активен