এক ডেটা স্ট্রাকচারে ফিংগার সার্চ হলো যেকোনো সার্চ অপারেশনের একটি এক্সটেনশন যা স্ট্রাকচারটি সাপোর্ট করে, যেখানে একটি রেফারেন্স (ফিংগার) একটি এলিমেন্টের ডেটা স্ট্রাকচারে দেওয়া থাকে কোয়েরির সাথে সাথে। যেখানে একটি এলিমেন্টের সার্চ টাইম অধিকাংশ কেসে ডেনোট করা হয় ডেটা স্ট্রাকচারে এলিমেন্টের সংখ্যা হিসেবে ফাংশন, ফিংগার সার্চ টাইম বিবেচিত হয় দূরত্বের ফাংশন হিসেবে এলিমেন্ট এবং ফিংগারের মাঝপথে।
m এলিমেন্টের একটি সেটে, দুটি এলিমেন্ট a এবং b-এর মধ্যে দূরত্ব d(a, b) তাদের র্যাঙ্কে পার্থক্য। যদি এলিমেন্ট a এবং b i-থ এবং j-থ লার্জেস্ট এলিমেন্ট হয় স্ট্রাকচারে, তবে র্যাঙ্কে পার্থক্য হলো |i - j|। যদি একটি নরমাল সার্চ কোনো স্ট্রাকচারে সাধারণত O(f(m)) টাইম নেয়, তবে এলিমেন্ট a-র জন্য ফিংগার সার্চ ফিংগার এলিমেন্ট b-সহ আদর্শভাবে O(f(d)) টাইম নিতে উচিত। দ্রষ্টব্য যে যেহেতু d ≤ m, তাই ফলো করে যে ওয়ার্স্ট কেসে, ফিংগার সার্চ শুধু নরমাল সার্চ όσο খারাপ। যাইহোক, প্র্যাকটিসে এই ডিজেনারেটেড ফিংগার সার্চ নরমাল সার্চের চেয়ে বেশি কাজ করে। উদাহরণস্বরূপ, যদি f(n) হলো log(n), এবং ফিংগার সার্চ ওয়ার্স্ট কেসে নরমাল সার্চের চেয়ে দুগুণ কমপেয়ারিজন করে, তাই ফলো করে যে ফিংগার সার্চ স্লোয়ার যখন d > √n। তাই ফিংগার সার্চ শুধু তখন বাস্তবায়ন করা উচিত যখন কেউ রিজনেবলি এক্সপেক্ট করতে পারে টার্গেট আসলে ফিংগার के নিকট।
বাস্তবায়ন (Implementations)
কিছু জনপ্রিয় ডেটা স্ট্রাকচার ফিংগার সার্চ সাপোর্ট করে বাস্তব স্ট্রাকচারে কোনো অ্যাডিশনাল চেঞ্জ ছাড়া। স্ট্রাকচার যেখানে এলিমেন্ট a সার্চ করা হয় একটি ইন্টারভ্যাল ন্যারো ডাউন করে যেতে a থাকতে পারে, সেখানে ফিংগার সার্চ এলিমেন্ট b থেকে টিপিক্যালি করা হয় সার্চ প্রসেস রিভার্স করে b থেকে যতক্ষণ না সার্চ ইন্টারভ্যাল যথেষ্ট বড় হয় এলিমেন্ট a কন্টেইন করতে, সেখানে সার্চ নরমালভাবে প্রসিড করে।
সর্টেড লিংকড লিস্ট (Sorted linked lists)
একটি লিংকড লিস্টে, কেউ সাধারণত লিনিয়ারলি সার্চ করে একটি এলিমেন্টের জন্য এক প্রান্ত থেকে অন্য প্রান্তে ট্রভার্স করে। যদি লিংকড লিস্ট সর্টেড থাকে, এবং আমাদের একটি রেফারেন্স থাকে কিছু নোডে যেটি এলিমেন্ট b ধারণ করে, তবে আমরা এলিমেন্ট a O(d) টাইমে খুঁজে পেতে পারি আমাদের সার্চ एलিমেন্ট b-থেকে শুরু করে।
সর্টেড অ্যারে (Sorted arrays)
একটি সর্টেড অ্যারে B-এ, কেউ সাধারণত বাইনারি সার্চ করে এলিমেন্ট a-র জন্য B-তে। ফিংগার সার্চ পারফর্ম করা হয় একটি ওয়ান-সাইডেড সার্চ বাস্তবায়ন করে B[j] = b থেকে। যতক্ষণ বাইনারি সার্চ সার্চ স্পেস হাফ করে প্রতিটি কমপেয়ারিজনের পর, ওয়ান-সাইডেড সার্চ সার্চ স্পেস ডাবল করে প্রতিটি কমপেয়ারিজনের পর। স্পেসিফিকলি, ওয়ান-সাইডেড সার্চের kth ইটারেশনে (a>b অনুমান করে), কনসিডারেশন আন্ডার ইন্টারভ্যাল হলো B[j, j+2k-1]。 এক্সপ্যানশন থামে যতক্ষণ না B[j + 2k-1] ≥ a, সেখান থেকে এই ইন্টারভ্যাল বাইনারি সার্চ করা হয় এলিমেন্ট a-র জন্য। যদি ওয়ান-সাইডেড সার্চ k ইটারেশন নেয় একটি ইন্টারভ্যাল খুঁজে বের করতে যেটি এলিমেন্ট a কন্টেইন করে, তবে ফলো করে যে d > 2k-2। এই রেঞ্জকে বাইনারি সার্চ করলে আরো k ইটারেশন লাগবে। অতএব, b থেকে a-র জন্য ফিংগার সার্চ O(k) = O(log d) টাইম কনসাম করে।
স্কিপ লিস্ট (Skip lists)
একটি স্কিপ লিস্টে, কেউ ফিংগার সার্চ করতে পারে এলিমেন্ট a-র জন্য একটি নোড থেকে যেটি এলিমেন্ট b ধারণ করে সিম্পলি সার্চ কন্টিনিউ করে এই পয়েন্ট থেকে। লক্ষ্য করুন যে যদি a < b, তবে সার্চ পिछ দিকে প্রসিড করে, এবং যদি a > b, তবে সার্চ সামনে দিকে প্রসিড করে। ব্যাকওয়ার্ড কেস নরমাল সার্চ ইন এ স্কিপ লিস্টের সাথে সিমেট্রিক, কিন্তু ফরওয়ার্ড কেস আসলে আরও জটিল। নরম্যালি, স্কিপ লিস্টে সার্চ এক্সপেক্টেড ফাস্ট কারণ লিস্টের শুরুতে সেন্টিনেল কনসিডার করা হয় ট্যালেস্ট নোড হিসেবে। যাইহোক, আمار ফিংগার হতে পারে একটি নোড অফ হাইট ১। এই কারণে, আমরা কদাচিৎ ক্লাইম করতে পারি সার্চ করার চেষ্টায়; কিছু যা নরম্যালি কখনো ঘটে না। যাইহোক, এমন কমপ্লিকেশন থাকলেও, আমরা O(log d) এক্সপেক্টেড সার্চ টাইম অর্জন করতে পারি।
ট্রিপস (Treaps)
একটি ট্রিপ হলো একটি র্যান্ডমাইজড বাইনারি সার্চ ট্রি (BST)। ট্রিপে সার্চিং সেম任何其他 BST-এ এলিমেন্ট সার্চ করার মতো। ট্রিপস যাইহোক প্রোপার্টি আছে যে দুটি এলিমেন্টের মাঝপথে এক্সপেক্টেড পাথ লেন্থ দূরত্ব d হলো O(log d)। তাই, এলিমেন্ট b ধারণকারী নোড থেকে এলিমেন্ট a-র জন্য ফিংগার সার্চ করতে, কেউ ট্রি ক্লাইম করতে পারে b এলিমেন্ট থেকে যতক্ষণ না a-র একটি অ্যানসেস্টর পাওয়া যায়, সেখান থেকে নরমাল BST সার্চ প্রসিড করে সাধারণভাবে। একটি নোড অন্য একটির অ্যানসেস্টর কিনা ক্যালকুলেট করা নন-ট্রিভিয়াল, কিন্তু কেউ ট্রি অগমেন্ট করতে পারে এই ফর্মের কোয়েরি সাপোর্ট করার জন্য এক্সপেক্টেড O(log d) ফিংগার সার্চ টাইম প্রদান করতে।
রোপস এবং ট্রি (Ropes and trees)
রোপ (ডেটা স্ট্রাকচার) বাস্তবায়ন সাধারণত একটি কর্ড পজিশন ইটেরেটর ব্যবহার করে স্ট্রিং ভিজিট করতে। ইটেরেটরকে একটি ফিংগার হিসেবে বিবেচনা করা যায় যা স্ট্রিং-এর কিছু স্পেসিফিক ক্যারেক্টারকে পয়েন্ট করে। অধিকাংশ ব্যালেন্সড ট্রির মতো, রোপস O(log(m)) টাইম নেয় একটি লিফ থেকে ডেটা রিট্রিভ করতে যখন শুধু ট্রির রুট দেওয়া থাকে। ট্রির প্রতিটি লিফ রিড করা প্রায়ই O(m*log(m)) টাইম লাগবে মনে হয়। যাইহোক, কিছু এক্সট্রা ইনফরমেশন স্টোর করে, ইটেরেটরকে বাস্তবায়ন করা যায় "দ্যা নেক্সট" লিফ রিড করতে শুধু O(1) টাইমে, এবং একটি ট্রির সব লিফ শুধু O(m) টাইমে।
