Umbali wa Hamming kwa Utaftaji wa Mseto katika SQLite

Hamming distance ni kipimo cha msingi cha mfanano ambacho huhesabu biti tofauti kati ya mifuatano miwili ya mfumo wa jozi, na kuifanya kuwa mojawapo ya mbinu za haraka na bora zaidi za takriban utafutaji wa jirani katika hifadhidata. Inapotumika kwa SQLite kupitia usanifu mseto wa utafutaji, Umbali wa Hamming hufungua uwezo wa utafutaji wa kimantiki wa kiwango cha biashara bila uendeshaji wa hifadhidata maalum za vekta.

Umbali wa Hamming Ni Nini na Kwa Nini Ni Muhimu kwa Utafutaji wa Hifadhidata?

Umbali wa kuhama hupima idadi ya nafasi ambapo nyuzi mbili za urefu sawa hutofautiana. Kwa mfano, nyuzi jozi 10101100 na 10001101 zina umbali wa Hamming wa 2, kwa sababu zinatofautiana katika nafasi mbili haswa. Katika miktadha ya utafutaji wa hifadhidata, hesabu hii inayoonekana kuwa rahisi inakuwa na nguvu isiyo ya kawaida.

Utafutaji wa jadi wa SQL unategemea ulinganifu kamili au uwekaji faharasa wa maandishi kamili, ambao unatatizika na ufanano wa kisemantiki - kutafuta matokeo ambayo maana kitu kimoja badala ya kushiriki manenomsingi yanayofanana. Umbali wa Hamming huziba pengo hili kwa kutumia misimbo ya heshi binary inayotokana na upachikaji wa maudhui, ikiruhusu hifadhidata kama SQLite kulinganisha mamilioni ya rekodi katika milisekunde kwa kutumia utendakazi wa XOR.

Kipimo kilianzishwa na Richard Hamming mnamo 1950 katika muktadha wa misimbo ya kusahihisha makosa. Miongo kadhaa baadaye, ikawa msingi wa urejeshaji habari, haswa katika mifumo ambayo kasi ni muhimu zaidi kuliko usahihi kamili. Kokotoo lake la O(1) kwa kila ulinganisho (kwa kutumia maagizo ya hesabu ya CPU) huifanya kufaa kipekee kwa injini za hifadhidata zilizopachikwa na nyepesi.

Je, Utafutaji Mseto Unachanganyaje Umbali wa Kuchanganya na Hoji za Jadi za SQLite?

Utafutaji mseto katika SQLite unachanganya mbinu mbili za urejeshaji zinazosaidiana: utafutaji wa maneno muhimu machache (kwa kutumia kiendelezi cha utafutaji cha maandishi kamili cha SQLite cha SQLite) na utafutaji mnene wa mfanano (kwa kutumia umbali wa Hamming kwenye upachikaji wa nambari za binary). Hakuna mbinu pekee inayotosha kwa mahitaji ya kisasa ya utafutaji.

Bomba la kawaida la utafutaji mseto hufanya kazi kama ifuatavyo:

1. Kizazi cha kupachika: Kila hati au rekodi hubadilishwa kuwa vekta ya sehemu ya juu ya kuelea kwa kutumia modeli ya lugha au chaguo la kukokotoa.
2. Ukadiriaji wa njia-mbili: Vekta ya kuelea inabanwa katika heshi ya binary iliyoshikana (k.m., biti 64 au 128) kwa kutumia mbinu kama vile SimHash au makadirio nasibu, na hivyo kupunguza kwa kiasi kikubwa mahitaji ya hifadhi.
3. Uhifadhi wa faharasa ya Hamming: Heshi binary huhifadhiwa kama safu wima INTEGER au BLOB katika SQLite, kuwezesha utendakazi wa haraka-haraka wakati wa hoja.
4. Ubao wa wakati wa hoja: Mtumiaji anapowasilisha swali, SQLite hukokotoa umbali wa Hamming kupitia kitendakazi maalum cha kufanya kazi kwa kutumia XOR na popcount, kurejesha wagombeaji waliopangwa kwa ulinganifu.
5. Muunganisho wa alama: Matokeo kutoka kwa utafutaji wa kisemantiki wa Hamming-based na utafutaji wa manenomsingi wa FTS5 yameunganishwa kwa kutumia Reciprocal Rank Fusion (RRF) au alama ya uzani ili kutoa orodha ya mwisho iliyoorodheshwa.

Upanuzi wa SQLite kupitia viendelezi vinavyoweza kupakiwa au vitendaji vilivyojumuishwa hufanya usanifu huu uweze kufikiwa bila kuhamia mfumo mzito zaidi wa hifadhidata. Matokeo yake ni injini ya utafutaji inayojitosheleza inayofanya kazi popote SQLite inaendesha - ikiwa ni pamoja na vifaa vilivyopachikwa, programu za simu, na uwekaji makali.

Maarifa Muhimu: Utafutaji wa Binary Hamming kwenye heshi-bit 64 una kasi ya takriban 30–50x kuliko ufanano wa cosine kwenye vekta kamili za float32 za dimensionality sawa. Kwa programu zinazohitaji kusubiri muda wa utafutaji wa milisekunde ya chini ya 10 katika mamilioni ya rekodi bila maunzi maalum, Umbali wa Hamming katika SQLite mara nyingi ni ubadilishanaji bora wa kihandisi kati ya usahihi na utendakazi.

Je, Sifa Zipi za Utendaji za Utafutaji wa Hamming katika SQLite?

SQLite ni hifadhidata ya faili moja, isiyo na seva, ambayo huunda vikwazo na fursa za kipekee za kutekeleza utafutaji wa umbali wa Hamming. Bila miundo asili ya kuorodhesha vekta kama vile HNSW au IVF (inayopatikana katika maduka mahususi ya vekta), SQLite inategemea uchanganuzi wa mstari kwa utafutaji wa Hamming - lakini hii ina kikomo kidogo kuliko inavyosikika.

Kokotoo la umbali wa biti 64 linahitaji XOR pekee ikifuatiwa na idadi ya watu (idadi ya watu, kuhesabu biti zilizowekwa). CPU za kisasa hutekeleza hili kwa maagizo moja. Uchanganuzi kamili wa mstari wa heshi milioni 1 za 64-bit hukamilika kwa takriban milisekunde 5-20 kwenye maunzi ya bidhaa, na kufanya SQLite kuwa ya vitendo kwa seti za data hadi rekodi milioni kadhaa bila mbinu za ziada za kuorodhesha.

Kwa seti kubwa zaidi za data, uboreshaji wa utendakazi hutokana na uchujaji wa awali wa mteuliwa: kwa kutumia vifungu vya WHERE vya SQLite ili kuondoa safu mlalo kwa metadata (masafa ya tarehe, kategoria, sehemu za watumiaji) kabla ya kutumia umbali wa Hamming, kupunguza ukubwa unaofaa wa skanisho kwa maagizo ya ukubwa. Hapa ndipo usanifu wa utafutaji mseto unapong'aa kwa kweli - kichujio kidogo cha maneno muhimu hufanya kama kichujio cha haraka, na umbali wa Hamming huwaweka tena nafasi za wagombea waliosalia.

Unatekelezaje Utendaji wa Umbali wa Hamming katika SQLite?

SQLite haijumuishi chaguo za kukokotoa asili za umbali wa Hamming, lakini API yake ya kiendelezi cha C hufanya utendakazi maalum wa scalar iwe rahisi kusajili. Kwenye Python kwa kutumia sqlite3 moduli, unaweza kusajili kitendakazi ambacho kinajumuisha umbali wa Hamming kati ya nambari mbili kamili:

Chaguo za kukokotoa hukubali hoja mbili kamili zinazowakilisha heshi jozi, hukokotoa XOR zao, kisha huhesabu biti zilizowekwa kwa kutumia bin().count('1') ya Python au mbinu ya upotoshaji wa haraka zaidi. Baada ya kusajiliwa, chaguo hili la kukokotoa linapatikana katika hoja za SQL kama vile chaguo za kukokotoa zilizojengewa ndani, kuwezesha hoja kama vile kuchagua safu mlalo ambapo umbali wa Hamming kwa heshi ya hoja huanguka chini ya kiwango, kinachopangwa kwa kupanda kwa umbali ili kupata mechi zilizo karibu zaidi kwanza.

Kwa utumaji wa uzalishaji, kuunda mantiki ya popcount kama kiendelezi cha C kwa kutumia API ya sqlite3_create_function ya SQLite hutoa utendakazi bora mara 10–100 kuliko Python iliyotafsiriwa, na kuleta utafutaji wa Hamming wa SQLite ndani ya ufikiaji wa hifadhidata maalum za vekta kwa kazi nyingi za vitendo.

Je!

Chaguo kati ya utafutaji wa Hamming unaotegemea SQLite na hifadhidata maalum za vekta kama vile Pinecone, Weaviate, au pgvector inategemea ukubwa, utata wa uendeshaji na vikwazo vya utumiaji. Utafutaji wa SQLite Hamming ni chaguo sahihi wakati usahili, kubebeka, na gharama ni jambo muhimu zaidi - ambayo ni kesi kwa idadi kubwa ya maombi ya biashara.

Hifadhi hifadhidata maalum za vekta huanzisha uendeshaji muhimu: miundombinu tofauti, muda wa kusubiri wa mtandao, utata wa ulandanishi, na gharama kubwa kwa kiwango. Kwa programu zinazohudumia makumi ya maelfu hadi mamilioni ya chini ya rekodi, utafutaji wa SQLite Hamming unatoa umuhimu unaolingana na mtumiaji na miundombinu ya sifuri ya ziada. Huweka pamoja faharasa yako ya utafutaji na data ya programu yako, ikiondoa aina nzima ya hali za kushindwa kwa mifumo iliyosambazwa.

Maswali Yanayoulizwa Sana

Je, utafutaji wa umbali wa Hamming ni sahihi vya kutosha kwa ajili ya programu za utafutaji wa uzalishaji?

Umbali wa kuongeza kasi kwenye upachikaji wa nambari za mfumo wa binary hubadilisha kiasi kidogo cha usahihi wa kukumbuka kwa faida kubwa za kasi. Kiutendaji, ujanibishaji wa mfumo wa jozi kwa kawaida hubakiza 90-95% ya ubora wa kukumbuka wa utafutaji wa mfanano wa float32 cosine. Kwa maombi mengi ya utafutaji wa biashara - ugunduzi wa bidhaa, kurejesha hati, misingi ya maarifa ya usaidizi kwa wateja - biashara hii inakubalika kabisa, na watumiaji hawawezi kutambua tofauti katika ubora wa matokeo.

Je, SQLite inaweza kushughulikia usomaji na uandishi unaofanana wakati wa hoja za utafutaji za Hamming?

SQLite inasaidia usomaji wa wakati mmoja kupitia hali yake ya WAL (Write-Ahead Logging), kuruhusu wasomaji wengi kuuliza kwa wakati mmoja bila kuzuia. Upatanisho wa uandishi ni mdogo - SQLite inasasisha huandika - lakini hii ni nadra sana kuwa kizuizi kwa mzigo mzito wa utafutaji ambapo uandishi haupatikani mara kwa mara na usomaji. Kwa matumizi ya utafutaji mseto wa kusoma sana, hali ya WAL ya SQLite inatosha kabisa.

Ukadiriaji jozi huathiri vipi mahitaji ya uhifadhi ikilinganishwa na vekta za kuelea?

Hifadhi iliyohifadhiwa ni kubwa. Upachikaji wa kawaida wa float32 wa 768-dimensional unahitaji baiti 3,072 (KB 3) kwa kila rekodi. Heshi ya binary ya biti 128 ya upachikaji sawa inahitaji baiti 16 tu - punguzo la 192x. Kwa mkusanyiko wa data wa rekodi milioni 1, hii ina maana tofauti kati ya GB 3 na MB 16 ya hifadhi ya kupachika, na kufanya utafutaji unaotegemea Hamming ufanyike katika mazingira yenye vikwazo vya kumbukumbu ambapo uhifadhi kamili wa kuelea hautawezekana.

Kujenga bidhaa mahiri na zinazoweza kutafutwa ndiyo aina hasa ya uwezo unaotenganisha biashara zinazokua na zilizodumaa. Mewayz ni Mfumo wa Uendeshaji wa biashara moja kwa moja unaoaminiwa na zaidi ya watumiaji 138,000, unaotoa moduli 207 zilizounganishwa - kutoka CRM na uchanganuzi hadi usimamizi wa maudhui na zaidi - kuanzia $19 pekee kila mwezi. Acha kuunganisha pamoja zana zilizokatika na anza kujenga kwenye jukwaa lililoundwa kwa mizani.

Anza safari yako ya Mewayz leo katika app.mewayz.com na ujionee kile ambacho mfumo wa uendeshaji wa biashara uliounganishwa unaweza kufanya kwa ajili ya timu yako.