रोजमर्रा की जिंदगी में आईटी के गैर-मानक अनुप्रयोग: पार्सिंग, अवधारणात्मक हैश, छवि तुलना = लागत अनुकूलन

इस लेख में मैं एक दिलचस्प समस्या के असामान्य समाधान के बारे में एक दिलचस्प कहानी साझा करना चाहता हूं जो एक साल पहले मेरे पास आई थी। लेख में वर्णित सब कुछ किया गया था, सबसे पहले, "सिर्फ मनोरंजन के लिए" और शुद्ध शैक्षणिक हित के बाहर ...
यह एक साल पहले था, बस खाली समय था और कुछ उपयोगी करने की इच्छा थी। स्पष्ट रूप से एक निश्चित बौद्धिक भूख और कुछ नया, कुछ दिलचस्प काम की तीव्र कमी थी ... इसलिए बाइक को छड़ी करने का प्रयास यहां तक ​​कि जहां यह बिल्कुल भी आवश्यक नहीं था ... वास्तव में, ऐसी बाइक सब कुछ नीचे वर्णित है ...

1. चुनौती

एक ट्रेडिंग और क्रय उद्यम में, खरीद अनुकूलन का मुद्दा तीव्र था। कंपनी के कई प्रमुख आपूर्तिकर्ता थे, लेकिन एक ही समय में, कई आपूर्तिकर्ताओं में 20-30% के पार माल थे, और सभी के लिए कीमतें अलग थीं। दुर्भाग्य से, अधिकांश सामान "पुरानी मेमोरी से" खरीदे गए थे, उदाहरण के लिए, उनका उपयोग इस तथ्य के लिए किया जाता है कि समूह ए के सामान को आपूर्तिकर्ता एक्स द्वारा आपूर्ति की जाती है, और समूह बी के सामान की आपूर्ति आपूर्तिकर्ता वाई द्वारा की जाती है, हालांकि यदि आप समूहों द्वारा नहीं बल्कि माल का चयन करते हैं, तो आप थोड़ा बचा सकते हैं। स्पष्टता के लिए, मैं एक उदाहरण दिखाऊंगा:

  आपूर्तिकर्ता X:
 उत्पाद A1 - 11 रूबल।
 उत्पाद ए 2 - 10 रूबल।
 उत्पाद बी 1 - 10 रूबल।
 उत्पाद बी 2 - 11 रूबल।

 आपूर्तिकर्ता Y:
 उत्पाद A1 - 10 रूबल।
 उत्पाद ए 2 - 11 रूबल।
 उत्पाद बी 1 - 11 रूबल।
 उत्पाद बी 2 - 10.5 रूबल।

तालिका से यह स्पष्ट है कि A1 और B2 "Y", और A2 और B2 से "X" खरीदना अधिक लाभदायक है। लेकिन यह नामकरण और 2 आपूर्तिकर्ताओं के 4 आइटमों के उदाहरण पर आसान और सरल है, और यदि आइटम हजारों आइटमों के दसियों और कुल आपूर्तिकर्ताओं के दर्जनों का योग करता है?
ऐसा लगता है कि समस्या एक प्रारंभिक कार्य है, लेकिन इसके लिए बहुत सरल गणनाओं की आवश्यकता होती है, वॉल्यूम आपके हाथों से नहीं बढ़ रहा है, इसलिए आपको इसे पीसी के कंधों पर जल्दी से स्थानांतरित करने और लाभ प्राप्त करने की आवश्यकता है? सब कुछ ऐसा होगा यदि सभी नामकरण और कीमतों के साथ एक ही आधार था। लेकिन अफसोस, यह एक यूटोपिया है ... आधार एक कचरे के ढेर की सामान्य, भयानक स्थिति में था, जिसमें केवल हर दिन जो लोग कचरे के इस ढेर को फेंकते थे, वे किसी तरह इसका पता लगा सकते थे। कीमतें और भी बदतर हैं, वे आम तौर पर विभिन्न कैटलॉग, कीमतों, साइटों में फैले हुए हैं। जब आप किसी तरह कैटलॉग करने की कोशिश करते हैं और इसे एक साथ रखते हैं, तो यह स्पष्ट हो जाता है कि मैन्युअल हस्तक्षेप के बिना यह बहुत मुश्किल है। एक आपूर्तिकर्ता निर्माता के लेख का उपयोग करता है, दूसरा अपना खुद का डालता है, और तीसरा उन्हें मूल्य सूची में बिल्कुल भी इंगित नहीं करता है। व्यावहारिक रूप से नाम कहीं भी मेल नहीं खाते हैं, उदाहरण के लिए, एक ही उत्पाद को कहा जा सकता है: "एक त्रिकोणीय पैटर्न की तस्वीर के साथ फूलदान", "फूलदान ए -563", "एक तस्वीर के साथ फूलना", अंत में, बस "फूल" :)
इसलिए, नाम से, कनेक्ट करना भी बिल्कुल बेकार था।

2. पागल विचार

और फिर एक पागल विचार आया। उत्पाद की बारीकियां ऐसी थीं कि लगभग हर जगह एक तस्वीर थी, इसके अलावा, आपूर्तिकर्ताओं ने अक्सर एक ही स्थान पर, या यहां तक ​​कि एक-दूसरे से भी तस्वीरें लीं। एक "ब्यूट" था, चित्र स्वाभाविक रूप से विभिन्न आकारों के थे, यहां तक ​​कि अनुपात भी भिन्न हो सकते थे। इसलिए तुलना "माथे पर" हमारी मदद नहीं करती है। लेकिन, आखिरकार, यांडेक्स किसी भी तरह की छवियां पाता है? हम इसे क्यों नहीं आजमाते?! हल!

साहित्य का अध्ययन करते हुए, Google, लेखों को पढ़कर, इस बात का अंदाज़ा हुआ कि इसी तरह की छवियों की खोज कैसे काम करती है। संक्षेप में: छवियों के हैश का निर्माण किया जाता है, और फिर हैश की तुलना और तुलना की जाती है। मुख्य अंतर हैश कार्यों में हैं। कार्यान्वयन में और गणना की बहुत जटिलता में, सबसे सरल और सबसे तेज़, अवधारणात्मक हैश है "औसत मूल्य द्वारा"।
संक्षेप में, ऑपरेशन का सिद्धांत: छवि को एक वर्ग में निचोड़ा जाता है, उदाहरण के लिए 16x16, फिर हम छवि को रंगीन छवि से ग्रेस्केल में प्राप्त करते हैं, फिर, वर्ग के बिंदुओं पर, हम औसत रंग मान की गणना करते हैं, और फिर दूसरे पास में हम 0 या 1 डालते हैं, जो इस पर निर्भर करता है इस बिंदु का रंग औसत मूल्य से कम या अधिक है। 0 और 1 का परिणामी क्रम वह हैश है जिसकी हम तलाश कर रहे हैं।

जल्दी से एक प्रोटोटाइप बनाने के लिए, छवि प्रसंस्करण के लिए ImageMagick का उपयोग करने का निर्णय लिया गया था, और php को स्क्रिप्टिंग भाषा के रूप में चुना गया था।
परीक्षणों के लिए एक सामग्री के रूप में, मैंने विंडोज के मानक सेट से "क्रिसेंटहैम.जेपीजी" छवि ली। पहली फ़ाइल जिसे मैंने test1.jpg कहा था, फिर मैंने स्रोत फ़ाइल ली और अनुपात को विकृत कर दिया, इसे test2.jpg नाम से सहेजा। तीसरे नमूने के रूप में, मैंने "डेजर्ट.जेपीजी" लिया और इसे test3.jpg नाम दिया। यहाँ वे हैं:



अगला, प्रीप्रोसेसिंग के लिए ImageMagick पर कॉल करें:

E:\ImageMagick\convert.exe E:\Article\img\test1.jpg -resize 16x16! -colorspace gray E:\Article\img\_test1.jpg E:\ImageMagick\convert.exe E:\Article\img\test2.jpg -resize 16x16! -colorspace gray E:\Article\img\_test2.jpg E:\ImageMagick\convert.exe E:\Article\img\test3.jpg -resize 16x16! -colorspace gray E:\Article\img\_test3.jpg 

हमें मिलता है:


अगला, हम खुद को हैश मानते हैं:

 <? function getPerceptHash($imgName) { $im = imagecreatefromjpeg($imgName); //    ,     256 (16*16),     $summ = 0; for($i=0;$i<8;$i++){ for($j=0;$j<8;$j++){ $summ += imagecolorat($im, $i, $j); } } $sred = $summ/64; //               0  1 $str=''; for($i=0;$i<8;$i++){ for($j=0;$j<8;$j++){ if(imagecolorat($im, $i, $j)>=$sred){ $str .= '1'; }else{ $str .= '0'; } } } //  16- ,   $str = base_convert($str, 2, 16); return $str; } echo '_test1.jpg '.getPerceptHash("E:\Denwer3\home\imagecomparer.loc\www\Article\img\_test1.jpg").'<br>'; echo '_test2.jpg '.getPerceptHash("E:\Denwer3\home\imagecomparer.loc\www\Article\img\_test2.jpg").'<br>'; echo '_test3.jpg '.getPerceptHash("E:\Denwer3\home\imagecomparer.loc\www\Article\img\_test3.jpg").'<br>'; ?> 

हमें इसका परिणाम मिलता है:

 _test1.jpg f9f6f0f0e0e0b0f000
 _test2.jpg fbf6f0f0c0b0f0000
 _test3.jpg 1e1e3e3e3e3e3c00

हम देखते हैं कि पहला और दूसरा हैश बहुत करीब हैं, और तीसरा भी करीब नहीं है। अन्य प्रयोगों की एक श्रृंखला भी आयोजित की गई थी, विधि काम करती है।

3. अभ्यास का प्रयास किया

तुलना विधि पाया जाता है, परीक्षण किया जाता है, यह परीक्षण मामलों पर काम करता है। युद्ध में इसकी जाँच करने का समय आ गया था। आपूर्तिकर्ताओं के कैटलॉग / मूल्य / साइटों और पार्सिंग के विभिन्न पार्सर्स को लिखने में कई दिन लग गए। सभी जानकारी + हैश डेटाबेस में जोड़े गए थे, और चित्र स्वयं डिस्क पर, आगे के प्रयोगों के लिए। कुल मिलाकर, लगभग 3 मिलियन रिकॉर्ड डेटाबेस में एकत्र किए गए थे।
शुरुआत में, विधि ने काम किया, लेकिन जैसे-जैसे आधार बढ़ता गया, परिणाम और बदतर होते गए, जब तक कि वे बस कूड़ेदान में नहीं लुढ़क गए। झूठी सकारात्मकता का एक समूह दिखाई दिया। विधि ने उन चित्रों पर अच्छी तरह से काम किया जो बस आकार देते थे, लेकिन अगर छवि को रंग-सही किया गया था, क्रॉप किया गया था, या इससे भी बदतर, एक वॉटरमार्क उस पर लागू किया गया था (जो बहुत, बहुत आम था), परिणाम खराब था।

4. पलाश

यह स्पष्ट था कि इस्तेमाल किया गया हैश फ़ंक्शन हमें शोभा नहीं देता है, हमें कुछ और गंभीर चाहिए। एक असतत कोसाइन परिवर्तन के आधार पर पीएचएश का उपयोग करने का निर्णय लिया गया

एल्गोरिथ्म अपने आप में भारी है और इसे php पर लागू करने का प्रयास कुछ अच्छे के साथ समाप्त नहीं हुआ। एसआई में कंसोल उपयोगिता बनाने के लिए समाधान था, जो इनपुट पर फ़ाइल का पथ प्राप्त करेगा, हैश को पढ़ेगा और इसे वापस करेगा। पुस्तकालय http://www.phash.org/ पाया गया था

फिर इस लाइब्रेरी का उपयोग करके एक परीक्षण नमूना जल्दी से लिखा गया है:

 #include "stdafx.h" #include <iostream> #include <windows.h> using namespace std; #ifndef _WIN32 typedef unsigned _uint64 ulong64; typedef signed _int64 long64; #else typedef unsigned long long ulong64; typedef signed long long long64; typedef unsigned char uint8_t; typedef unsigned int uint32_t; #endif typedef int (*ph_dct_imagehash)(const char* file,ulong64 &hash); int _tmain(int argc, TCHAR* argv[]) { if (argc > 1) { char* filename = (char *)malloc( 255 ); wcstombs( filename, argv[1], 255 ); ph_dct_imagehash _ph_dct_imagehash; HINSTANCE hInstLibrary = LoadLibrary(L"pHash.dll"); if (hInstLibrary) { _ph_dct_imagehash = (ph_dct_imagehash)GetProcAddress(hInstLibrary, "ph_dct_imagehash"); int err = 0; err = GetLastError(); ulong64 myhash=0; _ph_dct_imagehash(filename, myhash); std::cout << myhash << std::endl; FreeLibrary(hInstLibrary); } else { return 0; } }else{ return 0; } return 0; } 

हम संकलित करते हैं, हम आउटपुट - pHashConcole.exe पर प्राप्त करते हैं

Php से, इस निर्माण को नियमित एक्सएक्सएक्स के माध्यम से कहा जाता है:

 $pHash=exec('E:\Article\pHashConsole.exe "'.$filename.'"'); 

हैश को एक MySQL टेबल में बदल दिया गया था, और खोज परिणाम एक बहुत ही सरल क्वेरी के साथ प्राप्त किया जा सकता है:

 'SELECT * FROM (SELECT * , BIT_COUNT( hash ^ '.$pHash.') AS distance FROM images ORDER BY distance LIMIT 0 , 100) s1 WHERE distance < '.$precision.';' 

 जहां, $ फेश - एक हैश जिस पर हम समान हैं।
 $ सटीकता - सटीकता, अधिक, अधिक परिणाम होंगे, लेकिन मूल से दूर वे होंगे।  इसे अनुभवजन्य रूप से चुना जाता है।

फेश का उपयोग करके हमें न केवल स्केल की गई छवियों को खोजने की अनुमति दी गई, बल्कि उन चित्रों को भी दिखाया गया है जहां शिलालेख लागू किए गए थे, वॉटरमार्क, ऐसे भाग जहां रंग सुधार किए गए थे या काट दिए गए थे।

5. अंत!

इन सभी जोड़तोड़ों के परिणामस्वरूप, समस्या को हल करना और मैन्युअल विश्लेषण के बिना एक सामान्य आधार एकत्र करना संभव था, धन्यवाद जिसके कारण खरीद पर उद्यम की लागत का अनुकूलन करना संभव था। ऐसा प्रतीत होता है कि एक पागल विचार न केवल व्यवहार्य हो गया, बल्कि व्यवहार में भी उपयोगी था, जिसकी बदौलत एक मूर्त परिणाम प्राप्त हुआ।

यहां जानिए मजेदार कहानी ...

आपका ध्यान देने के लिए आप सभी का धन्यवाद! अंत!