تحلیل الگوریتم رتبه‌ بندی گوگل : معماری پردازش پیشنهادات خودکار

در این محتوا قصد دارم راجب پتنت US8713042B1 (Processing autocomplete suggestions) توضیح بدم و برسی کامل روش انجام بدم:

https://patents.google.com/patent/US8713042B1/en :

2012-10-11 Application filed by Google LLC | 2032-10-13 Adjusted expiration

نکته: موضوع پتنت معماری server-side محور است و تمرکز آن بر الگوریتم‌های پردازشی و سیستم امتیازدهی است.

مقدمه:

این پتنت درباره سیستمی است که وقتی شما در گوگل شروع به تایپ می‌کنید، به شما پیشنهادهایی می‌دهد. این سیستم از 8 بخش مختلف تشکیل شده که هر کدام وظیفه خاصی دارند.

در قلب این سیستم، یک موتور جستجو قرار دارد که با پایگاه داده بزرگی در ارتباط است. وقتی شما شروع به تایپ می‌کنید، هر حرفی که می‌نویسید به این موتور جستجو فرستاده می‌شود. موتور جستجو بلافاصله شروع به پیدا کردن کلمات و عباراتی می‌کند که ممکن است شما قصد نوشتن آنها را داشته باشید.

این سیستم می‌تواند روی انواع مختلف دستگاه‌ها کار کند - از کامپیوتر شخصی گرفته تا گوشی هوشمند و تبلت. مهم نیست از چه دستگاهی استفاده می‌کنید، سیستم خودش را با اندازه صفحه نمایش و نوع ورودی شما تطبیق می‌دهد.

نکته جالب اینجاست که سیستم فقط به دنبال کلمات کامل نمی‌گردد. حتی وقتی شما فقط یک یا دو حرف تایپ می‌کنید، سیستم می‌تواند حدس بزند که احتمالاً دنبال چه چیزی می‌گردید. این کار را با بررسی میلیون‌ها جستجوی قبلی که دیگر کاربران انجام داده‌اند، انجام می‌دهد.

برای هر پیشنهادی که سیستم می‌دهد، یک امتیاز در نظر گرفته می‌شود. این امتیاز بر اساس عواملی مثل تعداد دفعاتی که دیگران این کلمه را جستجو کرده‌اند، چقدر جدید است، و چقدر با چیزی که شما تایپ کرده‌اید مرتبط است، تعیین می‌شود.

وقتی پیشنهادها آماده شدند، سیستم آنها را به ترتیب امتیازشان مرتب می‌کند و بهترین‌ها را به شما نشان می‌دهد. این پیشنهادها معمولاً در یک منوی کشویی زیر جعبه جستجو نمایش داده می‌شوند. شما می‌توانید با کلیک کردن روی هر کدام از آنها، آن پیشنهاد را انتخاب کنید.

نکته مهم دیگر این است که سیستم به طور مداوم در حال یادگیری است. از انتخاب‌های کاربران یاد می‌گیرد و پیشنهادهایش را بهتر می‌کند. به همین دلیل است که با گذشت زمان، پیشنهادهای دقیق‌تر و مرتبط‌تری به شما می‌دهد.

این سیستم همچنین می‌تواند تشخیص دهد که آیا شما جستجویتان را تمام کرده‌اید یا نه. برای مثال، اگر دکمه جستجو را بزنید یا کلید Enter را فشار دهید، سیستم می‌فهمد که جستجوی شما کامل شده است.

هدف نهایی این سیستم، صرفه‌جویی در وقت شماست. به جای اینکه مجبور باشید تمام کلمه یا عبارت را تایپ کنید، می‌توانید با تایپ چند حرف اول و انتخاب از بین پیشنهادها، سریع‌تر به نتیجه برسید.

این سیستم (گوگل ساجست) به طور مداوم در حال به‌روزرسانی و بهبود است و هر روز هوشمندتر می‌شود تا بتواند پیشنهادهای بهتری به کاربران ارائه دهد.

برسی نحوه عملکرد با شرح تصویر:

شکل ۱: نمودار بلوکی از یک محیط نمونه که در آن پیاده‌سازی روش پردازش پیشنهادهای تکمیل خودکار می‌تواند اجرا شود.

دستگاه کاربر (شماره 130)
موتور جستجو (شماره 105)
پایگاه داده محتوا (شماره 115)
موتور پیشنهادات خودکار (شماره 110)
پردازشگر پیشنهادات (شماره 120)
شبکه ارتباطی (شماره 101)

همه این اجزا با هم در ارتباط هستند و یک چرخه کامل را تشکیل می‌دهند.

شکل ۲: نمودار جریانی که روش نمونه تعیین پیشنهادهای تکمیل خودکار، تعیین امتیازها برای پیشنهادهای تکمیل خودکار و مرتب‌سازی پیشنهادهای تکمیل خودکار را نشان می‌دهد.

200 - دریافت اولیه: شناسایی تعدادی از پیشنهادات تکمیل خودکار و امتیازهای مربوط به این پیشنهادات برای یک پرسش جزئی.
205 - تولید پیشنهادات: تولید پیشنهادات اضافی برای پیشنهادات تکمیل خودکار به‌دست‌آمده که دارای چندین واژه هستند.
210 - امتیازدهی: تخصیص امتیازهای اضافی به پیشنهادات اضافی.
215 - گروه‌بندی: شناسایی گروه‌هایی از ورودی‌های مشابه در میان پیشنهادات اضافی و پیشنهادات تکمیل خودکار شناسایی‌شده.
220 - تجمیع امتیازها: تعیین یک امتیاز تجمیع‌شده برای هر یک از گروه‌های ورودی‌های مشابه.
225 - مرتب‌سازی: مرتب‌سازی پیشنهادات تکمیل خودکار و پیشنهادات اضافی بر اساس امتیازهای آن‌ها.

شکل ۳الف: فهرست نمونه‌ای از پیشنهادهای تکمیل خودکار و امتیازهای متناظر آنها برای یک پرس‌وجو.

شکل ۳ب: فهرست پیشنهادهای تکمیل خودکار شکل ۳الف، به همراه پیشنهادهای تکمیل خودکار اضافی تولید شده و امتیازهای متناظر آنها.

شکل ۳: فهرست پیشنهادهای تکمیل خودکار شکل ۳ب، همراه با گروه‌های ورودی‌های مشابه و امتیازهای ترکیب شده متناظر آنها.

تصویر 3A - لیست پیشنهادات اولیه:

پیشنهادات و امتیازها:

تعطیلات (vacation): 4.0
ویدیو (video): 2.0
تاکستان (vineyard): 2.5
مقصد تعطیلات: 3.6
نرم‌افزار ویرایش ویدیو: 2.1
تاکستان در دره ناپا: 1.0
تعطیلات تاکستان در توسکانی: 1.0

تصویر 3B - پیشنهادات گسترش یافته:

پیشنهادات با امتیازهای جدید:

تعطیلات: 4.0
ویدیو: 2.0
تاکستان: 2.5
مقصد تعطیلات: 3.6
تعطیلات [از مقصد]: 3.6
ویرایش ویدیو: 2.1
ویدیو: 2.1
تاکستان در: 1.0

تصویر 3C - پیشنهادات نهایی و تجمیع شده:

نتایج نهایی با امتیازهای تجمیعی:

تعطیلات: 10.8
ویدیو: 4.1
تاکستان: 3.5
مقصد تعطیلات: 3.6
ویرایش ویدیو: 2.1
تاکستان در: 2.5

شکل ۴: نمودار جریانی که روش نمونه تعیین اینکه کدام پیشنهادهای تکمیل خودکار برای نمایش روی دستگاه محاسباتی ارائه شوند را نشان می‌دهد.

· مرحله 400: دریافت فهرستی از پیشنهادات تکمیل خودکار و امتیازهای مربوط به آن‌ها برای یک پرسش.

· مرحله 405: شناسایی داده‌های نمایش صفحه که نشان‌دهنده تعداد پیشنهادات تکمیل خودکار است که باید به‌طور همزمان نمایش داده شوند.

· مرحله 410: شناسایی یک پیشنهاد تکمیل خودکار در فهرست که دارای یک پیشنهاد تکمیل خودکار طولانی‌تر مربوطه در فهرست است.

· مرحله 415: تعیین اینکه آیا باید پیشنهاد تکمیل خودکار شناسایی‌شده را به عنوان یک پیشنهاد تکمیل خودکار نمایش داد و آیا باید پیشنهاد تکمیل خودکار طولانی‌تر مربوطه را نیز به عنوان یک پیشنهاد تکمیل خودکار نمایش داد.

· مرحله 420: ارائه پیشنهاد تکمیل خودکار شناسایی‌شده و/یا پیشنهاد تکمیل خودکار طولانی‌تر برای نمایش.

شکل ۵: نمودار جریانی که یک روش نمونه دیگر برای تعیین اینکه کدام پیشنهادهای تکمیل خودکار برای نمایش روی دستگاه محاسباتی ارائه شوند را نشان می‌دهد.

مرحله ۵۰۰: سوال اول

سیستم بررسی می‌کند که آیا پیشنهاد ورودی فقط یک کلمه است؟

مرحله ۵۰۵: مسیر "بله"

اگر پیشنهاد فقط یک کلمه باشد
بدون هیچ شرط دیگری، مستقیماً آن را به لیست نمایش اضافه می‌کند

مرحله ۵۱۰: مسیر "خیر" و سوال دوم

اگر پیشنهاد بیش از یک کلمه است
سیستم بررسی می‌کند که آیا طولانی‌ترین پیشوند این پیشنهاد در لیست نمایش موجود است
و اگر هست، آیا فاصله‌اش تا انتهای لیست کمتر از "X ضربدر تعداد صفحات" است؟
مثال: اگر X=2 و هر صفحه 5 مورد دارد، یعنی حداکثر 10 مورد بالاتر قابل قبول است

مرحله ۵۱۵: سوال سوم

اگر شرط مرحله ۵۱۰ برقرار بود
سیستم امتیاز پیشنهاد فعلی را با امتیاز طولانی‌ترین پیشوند مقایسه می‌کند
بررسی می‌کند که آیا امتیاز پیشنهاد حداقل Y درصد امتیاز پیشوند است؟
مثال: اگر Y=80، یعنی امتیاز پیشنهاد باید حداقل 80% امتیاز پیشوند باشد

مرحله ۵۲۰ و ۵۲۵: اقدامات نهایی مسیر مثبت

اگر همه شرایط بالا برقرار بود:

پیشنهاد جدید به لیست نمایش اضافه می‌شود (۵۲۰)
سپس طولانی‌ترین پیشوند از لیست حذف می‌شود (۵۲۵)

مرحله ۵۳۰: مسیر "خیر"

اگر هر کدام از شرط‌های بالا برقرار نبود
پیشنهاد فعلی به لیست اضافه نمی‌شود

مثال عملی:

- X = 2 (یعنی حداکثر دو برابر طول صفحه)

- Y = 80 (یعنی حداقل 80% امتیاز)

- پیشنهاد: "هتل های پاریس"

- پیشوند موجود در لیست: "هتل های"

اگر:

1. "هتل های" در فاصله مناسبی از انتهای لیست باشد

2. امتیاز "هتل های پاریس" حداقل 80% امتیاز "هتل های" باشد

نتیجه:

- "هتل های پاریس" اضافه می‌شود

- "هتل های" حذف می‌شود

شکل ۶: نمای جزئی از یک تصویر صفحه نمایش محیط نمونه که می‌تواند برای ارائه نتایج پیشنهادهای تکمیل خودکار به کاربر استفاده شود.

شکل ۷: نمای جزئی دیگری از یک تصویر صفحه نمایش محیط نمونه که می‌تواند برای ارائه نتایج پیشنهادهای تکمیل خودکار به کاربر استفاده شود.

شکل ۶ (نمای عمودی): کل نمای رابط کاربری

۶۰۰ : کادر جستجو که با حرف "v" شروع شد

لیست پیشنهادات به صورت عمودی:

1. ویدیو

2. مقصد تعطیلات

3. داستان‌های خون‌آشام

4. موتورهای جستجوی تعطیلات

5. تاکستان در ناپا

6. تعطیلات در تاکستان

شکل ۷ (نمای افقی): کل نمای رابط کاربری

۷۰۰: نمایش افقی نتایج جستجو برای حرف "v"

- چهار نتیجه در یک ردیف:

۷۲۰الف: ویدیو

۷۲۰ب: مقصد تعطیلات

۷۲۰داستان‌های خون‌آشام

۷۲۰د: موتورهای جستجوی تعطیلات

شکل ۸: نمودار بلوکی از یک سیستم کامپیوتری نمونه.

برسی معماری ذخیره‌سازی:

نکته : این بخش فرضیه ایی بر اساس متن های پتنت است.

سیستم از یک معماری چند لایه‌ای پیچیده تشکیل شده که در لایه اصلی ذخیره‌سازی، تمام اطلاعات مربوط به جستجوها شامل شناسه یکتا، متن جستجو، زمان، اطلاعات کاربر، موقعیت جغرافیایی، و آمار تعامل ذخیره می‌شود. این داده‌ها با جدول پیشنهادات جستجو که شامل پیشوندها، متن‌های پیشنهادی کامل، امتیازات و فرکانس‌های استفاده است، ترکیب می‌شود. جدول آمار جستجو نیز داده‌های تجمعی شامل تعداد کل، میانگین‌های روزانه و روندهای هفتگی را نگهداری می‌کند.

در لایه ارتباطات، سیستم روابط بین جستجوها را با ثبت جستجوهای مرتبط، نوع ارتباط و وزن آن مدیریت می‌کند و همزمان دسته‌بندی جستجوها را با الگوها و امتیازات اطمینان نگه می‌دارد. لایه کش و بهینه‌سازی با استفاده از هش پیشوندها، پیشنهادات پرکاربرد را در حافظه نگه می‌دارد و جستجوهای محبوب را با امتیازات محبوبیت و فرکانس به‌روزرسانی مدیریت می‌کند.

لایه زبان و منطقه، مدیریت جستجوها در زبان‌ها و مناطق مختلف را بر عهده دارد و شامل نرمال‌سازی متون و تحلیل روندهای منطقه‌ای است. لایه تحلیلی با ثبت الگوهای جستجو و رفتار کاربران، داده‌های عمیق‌تری برای تحلیل و بهبود سیستم فراهم می‌کند.

سیستم از ویژگی‌های کلیدی مانند پارتیشن‌بندی (زمانی، جغرافیایی و زبانی)، ایندکس‌گذاری چندسطحی و مکانیزم‌های بهینه‌سازی بهره می‌برد. مکانیزم‌های کلیدی شامل به‌روزرسانی‌های آنی و دوره‌ای، انواع مختلف جستجو (پیشوندی، فازی و معنایی) و سیستم‌های رتبه‌بندی پیشرفته است.

امنیت سیستم با مکانیزم‌های کنترل دسترسی، محدودیت‌های جغرافیایی و زمانی، و سیستم‌های پشتیبان‌گیری تضمین می‌شود. مکانیزم‌های نگهداری شامل پاکسازی خودکار داده‌های قدیمی، بهینه‌سازی فضا و سیستم‌های مانیتورینگ جامع است که عملکرد، خطاها و دسترسی‌ها را پایش می‌کنند.

این معماری پیچیده به سیستم اجازه می‌دهد تا میلیاردها جستجو را در روز پردازش کند، پیشنهادات را در کمتر از 100 میلی‌ثانیه ارائه دهد، و همزمان امنیت، کارایی و قابلیت اطمینان بالا را حفظ کند. سیستم به صورت مداوم خود را با الگوهای جدید جستجو تطبیق می‌دهد و با استفاده از داده‌های تحلیلی، کیفیت پیشنهادات را بهبود می‌بخشد.

سوالات متداول:

آیا امتیازدهی پیشنهادات بر اساس رفتار کاربران قبلی است؟

بله. سیستم از "لیست جستجوهای گذشته کاربران" و "پرس و جوهای تولید شده خودکار" استفاده می‌کند و امتیازها بر اساس میزان محبوبیت و استفاده قبلی تعیین می‌شوند.

چگونه سیستم با کلمات مرکب مثل "new york" برخورد می‌کند؟

سیستم از "قوانین یکسان‌سازی" استفاده می‌کند که کلمات مرکب رایج را به عنوان یک واحد در نظر می‌گیرد. مثلاً فاصله بین "new" و"york" به عنوان مرز کلمه شناخته نمی‌شود.

آیا stop words در پیشنهادات تأثیر دارند؟

بله. سیستم از لیستی از stop words استفاده می‌کند و از ایجاد پیشنهادات اضافی در مرز این کلمات جلوگیری می‌کند. مثلاً برای کلماتی مثل"and" و "of".

نحوه اولویت‌بندی پیشنهادات طولانی‌تر نسبت به کوتاه‌تر چگونه است؟

اگر امتیاز پیشنهاد طولانی‌تر حداقل Y% (معمولاً بین 25% تا 33%) امتیاز پیشنهاد کوتاه‌تر باشد، ممکن است به جای آن نمایش داده شود.

آیا سیستم از stemming استفاده می‌کند؟

بله، در بخش قوانین یکسان‌سازی از stemming برای شناسایی و تجمیع موارد مشابه استفاده می‌شود.

چگونه سیستم با دستگاه‌های مختلف (موبایل/دسکتاپ) سازگار می‌شود؟

سیستم از page display data استفاده می‌کند که شامل اطلاعات اندازه صفحه، رزولوشن و جهت صفحه است و پیشنهادات را متناسب با آن تنظیم می‌کند.

آیا سیستم از real-time suggestions پشتیبانی می‌کند؟

بله، علاوه بر پیشنهادات ذخیره شده، سیستم قابلیت تولید پیشنهادات real-time را نیز دارد.

نحوه مدیریت synonyms چگونه است؟

سیستم می‌تواند کلمات و عبارات مشابه (مثل مترادف‌ها یا اصلاحات املایی) را در پیشنهادات لحاظ کند.

چگونه سیستم امتیازهای تجمیعی را محاسبه می‌کند؟

امتیاز تجمیعی از جمع امتیازهای فردی پیشنهادات مشابه محاسبه می‌شود. مثلاً اگر"video" سه بار با امتیازهای 2.0، 2.1 و 1.5 ظاهر شود، امتیاز تجمیعی آن 5.6 خواهد بود.

آیا ترتیب کلمات در پیشنهادات مهم است؟

بله، سیستم به ترتیب کلمات حساس است و پیشنهادات را بر اساس کلمه اول و کلمات متوالی بعدی تجزیه می‌کند.

نحوه مدیریت پیشنهادات چند زبانه چگونه است؟

پتنت مستقیماً به این موضوع اشاره نکرده، اما سیستم می‌تواند برای هر زبان مجموعه قوانین یکسان‌سازی و stop words مخصوص داشته باشد.

آیا فرکانس به‌روزرسانی پیشنهادات قابل تنظیم است؟

بله، سیستم می‌تواند در حالت real-time یا offline کار کند و فرکانس به‌روزرسانی بر اساس نیاز قابل تنظیم است.

چگونه سیستم با عبارات تخصصی یا اصطلاحات خاص برخورد می‌کند؟

سیستم می‌تواند از لیست‌های اصطلاحات خاص استفاده کند و آنها را به عنوان یک واحد در نظر بگیرد، مشابه رفتار با "new york".

تأثیر سرعت تایپ کاربر در پیشنهادات چیست؟

سیستم می‌تواند بر اساس وقفه‌های بین کاراکترها عمل کند و در صورت مکث طولانی‌تر کاربر، آن را به عنوان پایان query در نظر بگیرد.

آیا سیستم می‌تواند رفتار فصلی یا زمانی را در نظر بگیرد؟

اگرچه مستقیماً ذکر نشده، اما سیستم می‌تواند از طریق به‌روزرسانی مداوم امتیازها بر اساس رفتار کاربران، روندهای فصلی را منعکس کند.

نحوه مدیریت پیشنهادات برای عبارات منفی چگونه است؟

سیستم می‌تواند علائم خاص مثل "-" را شناسایی کند و پیشنهادات را متناسب با آن تنظیم کند.

آیا سیستم می‌تواند پیشنهادات را بر اساس موقعیت جغرافیایی شخصی‌سازی کند؟

اگرچه در پتنت مستقیماً اشاره نشده، اما سیستم می‌تواند از داده‌های موقعیتی برای شخصی‌سازی پیشنهادات استفاده کند.

آیا سیستم می‌تواند پیشنهادات را بر اساس دسته‌بندی موضوعی ارائه دهد؟

بله، سیستم می‌تواند پیشنهادات را بر اساس دسته‌بندی‌های موضوعی گروه‌بندی و امتیازدهی کند.

مقایسه پتنت US8700653B2 با US8713042B1 :

تفاوت‌های بنیادی این دو پتنت را می‌توان در چند محور اصلی بررسی کرد. پتنت (Predictive query completion and predictive search results) US8700653B2 عمدتاً بر روی رابط کاربری و مکانیزم تعاملی تمرکز دارد، جایی که هدف اصلی آن ایجاد یک تجربه کاربری یکپارچه در فرآیند جستجو است. این پتنت توضیح می‌دهد چگونه دستگاه کاربر (client device) یک رابط جستجو را با قابلیت ورود کوئری ایجاد می‌کند و چطور کاراکترهای وارد شده را به سرویس جستجو به عنوان درخواست پیشنهاد ارسال می‌کند. نکته قابل توجه این است که این پتنت روی نمایش نتایج جستجو به صورت مستقل از انتخاب کاربر تمرکز دارد، یعنی حتی قبل از اینکه کاربر یک پیشنهاد را انتخاب کند یا جستجوی کامل را ارسال کند، نتایج مرتبط نمایش داده می‌شوند.

در مقابل، پتنت (Processing autocomplete suggestions) US8713042B1 بیشتر بر روی مکانیزم‌های پشت صحنه و پردازش پیشنهادهای خودکار تمرکز دارد. این پتنت به جای تمرکز بر نحوه نمایش، روی نحوه تولید و پردازش پیشنهادهای تکمیل خودکار تأکید می‌کند. یکی از ویژگی‌های کلیدی این پتنت، توانایی آن در تولید پیشنهادهای اضافی برای عبارات چند کلمه‌ای و تعیین امتیاز برای این پیشنهادهات است. همچنین، این پتنت شامل مکانیزمی برای شناسایی و ترکیب موارد مشابه در بین پیشنهادها و ایجاد یک امتیاز ترکیبی برای هر مورد تجمیع شده است.

خلاصه از تفاوت‌های کلیدی :

هدف و تمرکز:

US8700653B2: تمرکز بر تجربه کاربری و نمایش نتایج پیش‌بینانه

US8713042B1: تمرکز بر الگوریتم‌های پردازشی و سیستم امتیازدهی

لایه عملکردی:

US8700653B2: عملکرد در لایه رابط کاربری (Front-end)

US8713042B1: عملکرد در لایه پردازشی (Back-end)

مکانیزم اصلی:

US8700653B2: پیش‌بینی و نمایش نتایج قبل از تکمیل جستجو

US8713042B1: پردازش و ترکیب پیشنهادهای خودکار

خروجی نهایی:

US8700653B2: نمایش نتایج جستجو به صورت پیش‌بینانه

US8713042B1: تولید و رتبه‌بندی پیشنهادهای بهینه‌شده

نوآوری اصلی:

US8700653B2: ارائه نتایج بدون نیاز به تکمیل یا انتخاب کوئری

US8713042B1: سیستم هوشمند ترکیب و امتیازدهی پیشنهادها

این دو پتنت در واقع مکمل یکدیگر هستند و با هم یک سیستم جامع برای بهبود تجربه جستجوی کاربر ایجاد می‌کنند. در حالی که یکی روی بهینه‌سازی تعامل کاربر تمرکز دارد، دیگری روی بهبود کیفیت و دقت پیشنهادها متمرکز است. ترکیب این دو فناوری منجر به ایجاد یک سیستم جستجوی پیشرفته و کاربرپسند می‌شود که هم سرعت و هم دقت بالایی دارد.