Linux за българи: Форуми

Програмиране => Общ форум => Темата е започната от: console в Feb 06, 2019, 16:33



Титла: Търсене и съвпадения
Публикувано от: console в Feb 06, 2019, 16:33
Здравейте,

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

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

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

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

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

Основното ми питане е какъв език е най-добре да се изоолзва за да минава бързо процеса. Пробвах с php и не ме изкефи изобщо защото за около 560 продукта подадени от клиенти цялото мачване през стотиците записи от таблицата с продукти мина за около 20 мин. То са вярно и лаптопа дето тествах не е много мощен но все пак 20 минути ми се сториха адски много за такъв тип операция.


Титла: Re: Търсене и съвпадения
Публикувано от: makeme в Feb 06, 2019, 16:40
Здравейте,

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

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

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

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

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

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


Титла: Re: Търсене и съвпадения
Публикувано от: jet в Feb 06, 2019, 21:29
Не става ясно каква е тази база данни, но дано не е SQLite.
Ако e MySQL едва ли Php е нещото дето я бави. Разгледай заявките които правиш дали не връщат много записи въртяни в цикъл.


Титла: Re: Търсене и съвпадения
Публикувано от: spec1a в Feb 06, 2019, 21:57
   Не си написал каква е базата данни.
   Аз бих заложил на С++ , да,по-сложно е,изисква повече писане на код,
но е номер 1 по бързодействие при езиците от високо ниво.


Титла: Re: Търсене и съвпадения
Публикувано от: 4096bits в Feb 06, 2019, 22:58
Хм! Не, че съм се занимавал с бази данни, обаче който и език да се използва, търсенето няма ли да се направи на практика от самата база данни? Програмния език просто има библиотека, която е интерфейс към нея, за да може да си говорят... Или нещо бъркам?


Титла: Re: Търсене и съвпадения
Публикувано от: remotexx в 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


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

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


Титла: Re: Търсене и съвпадения
Публикувано от: 4096bits в Feb 07, 2019, 09:24
Три-четири реда примерни реда от csv-то?
Впрочем, защо не правиш заявка директо към базата данни?


Титла: Re: Търсене и съвпадения
Публикувано от: console в 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 би трябвало да свърши перфектна работа.


Титла: Re: Търсене и съвпадения
Публикувано от: Naka в 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.





Титла: Re: Търсене и съвпадения
Публикувано от: makeme в Feb 07, 2019, 11:49
Впечатляващо е как grep работи. Файла с продуктите от базата е над 300МБ и grep намира съвпадения за по малко от секунда. Явно с него и някъв regex би трябвало да свърши перфектна работа.
Ако работиш с текстови файлове (тхт, цсв или дори дъмп) грепа е твоето нещо. Идеята е че тогава отпада това което ти предложих за ССД-то. 1вия греп може да ти мине по-бавничко, но след това всички файлове отиват в кеш буфера (рамта) и греповете минават даже за много под секунда.

ПП: При postgre не знам как е, но това е идеята на innodb при mysql. Вдигаш буфера и се получава същото. Просто хардовете са ужасни за много текст на едно място :)


Титла: Re: Търсене и съвпадения
Публикувано от: remotexx в Feb 07, 2019, 16:50
Solr


Титла: Re: Търсене и съвпадения
Публикувано от: Odido в Feb 07, 2019, 19:36
Solr
Оха,1400 страници гайд.Ама изглежда доста интересно.


Титла: Re: Търсене и съвпадения
Публикувано от: 4096bits в Feb 07, 2019, 21:12
За това ($2) ли става въпрос?
Има и една библиотека за Питон - asyncpg ($2) - използваща asyncio, но не ми се е налагало да я ползвам. На хартия изглежда добре. Ако се включи и Nuitka ($2) в играта, може да стане наистина интересно.

https://magic.io/blog/asyncpg-1m-rows-from-postgres-to-python/


Титла: Re: Търсене и съвпадения
Публикувано от: remotexx в 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


Титла: Re: Търсене и съвпадения
Публикувано от: Naka в Feb 09, 2019, 11:49
Искам нещо нещо да добавя. Всички тези алгоритми levenshtein, или soundex и т.н а също и търсачките (mysql fulltext search) работят добре само за английски. (За  Solr не съм сигурен, но не мисля, че знае особеностите на българският)

В примера който дадох (за inverted index), много добри резултaти се получават ако всички думи се заменят с корените им- и в индекса и това което подава клиента. Така търсенето става независимо дали клиента е въвел [computer] или [computers]. А и самият индекс става много по малък (най-малко наполовина) а също и още по-бърз.

И тук за английският е много лесно. Например computer, computers, computing, computed -> имат един корен computer (а може и compute). Някъде в нета имаше някъде един алгоритъм за намиране на корените в английският и той беше само двайсетина реда.

Обаче за BG е направо ужастъ. Имаме компютър, компютри, компютрите, компютърът, компютъра. проблема е че в бг, не можеш винаги да махнеш направо суфиксите (*и, *ът, *а), защото думата често се изменя. 

компютър->компютър, компютр(и)->компютр,
Някъде имаше статия (тук в linux-bg за спелинга на бг) че имало 100+ словоформи.

http://www.referati.org/formalizaciqta-na-bylgarskiq-ezik-i-razrabotkata-na-lingvistichen-procesor-morfologiq/41514/ref/p2
http://www.referati.org/formalizaciqta-na-bylgarskiq-ezik-i-razrabotkata-na-lingvistichen-procesor-morfologiq/41514/ref






Титла: Re: Търсене и съвпадения
Публикувано от: remotexx в Feb 09, 2019, 18:12
Ами ако иска - нека си напише каквото си иска индексиране, а дали и колко ще се справи е отделен въпрос. Аз затова предложих - и отново предлагам, степенувани от най-лесното към най-трудното различни методи:
1) Десктоп търсачка (не съм много сведущ по темата - помагайте) - според тия най-новата суер дупер (т.е. поредна промяна/подмяна) е тази (която се ползва в линукс) - Recoll ($2)
2) Някаква БД с вградено пълно текстово индексиране - MySQL като най-лесна и (забележи) предлага да си качиш собствена добавка за напр. български
3) Solr - което и най-доброто за търсене в целия текст
4) сам да си напише - каквото му душа сака...
5) всяко друго нещо което ще му изгради индекс, че без индекс ще е много бавно... както го беше почнал той - без индекс, и всеки път почва да върти цикъла отначало и почва сравняването отначало.

по въпроса за soundex - българския (за разлика от английския) е фонетичен език така че няма нужда да се търси по фонетично съвпадение (ако думата съвпада както си е написана, то тя съвпада и фонетично) (не е като френския напр. половината букви не се четат или английския пише едно а се чете друго - C'est la vie)

и накрая Левенщайн и/ли която и да е др. метрика дето мери разстоянието между думите/фразите ще си работи перфектно. напр. Solr (предполагам и MySQL и др.) пак ще изкара и по-малко вероятните съвпадения но с по-малко вероятност - и понеже БГ е фонетичен как мислите кое ще по-по-най- близо до оригинала...
напр. (предполагаме че продавачките са много тъпи и са ги записали така)
32 бр. компоти vs. 32 гб компютър
предплагаем изход от Солр-а:
'32 гб компютър'  - 100%
'32 гб компютри'  - 95% - не виждам как на фонетичен език/азбука нещо различно от търсеното ще мачва по-добре
'32 гб компютъри' - 95%
'32 бр. компоти'    - 50%
...
'32 бр ножчета за бръснене' - 5% (това последното ако го настроите да показва всички - иначе спира около 70-80% или 100 бр. съвпадения... или нещо такова ми се върти)


Титла: Re: Търсене и съвпадения
Публикувано от: Naka в Feb 09, 2019, 20:13
Е тук се дават идеи.  [_]3

Освен soundex() има и metaphone() което било много по добро. В задачата се пита защо в базата съм си оставил поле наречено metaphone ??? Е това не мога да се сетя.

За да мачва правилно трябва първо кирилският стринг да се прекара през транслитерация и след това metaphone(). Всеки може лесно да си направи експерименти през конзолното php.

Индекса например може да се направи не чрез униканите думи, а чрез metaphone представянето. Така още повече ще се свие, ще стане още по-бърз а и търсенето би трябвало да се подобри.