3.3　實際應用

在給定的數據存儲庫中高效、準確地查找數據的能力對許多現實生活中的應用至關重要。根據你所選擇的查找算法，你可能還需要先對數據進行排序。恰當地排序和選擇查找算法將取決于數據的類型和規模以及你要求解的問題的性質。

讓我們嘗試使用本章介紹的算法來解決某國移民部門將一個新的申請人與其歷史記錄進行匹配的問題。當有人申請簽證進入該國時，系統會嘗試將申請人與現有的歷史記錄進行匹配。如果找到至少一個匹配項，則系統會進一步計算此人過去被批準或被拒絕的次數。另一方面，如果沒有找到匹配的記錄，系統會將申請人歸類為新的申請人，并給其發一個新的識別碼。在歷史數據中查找、定位和識別一個人的能力對系統至關重要。這一信息很重要，因為如果某人在過去申請過，并且知道申請被拒絕了，那么這可能會對此人當前的申請產生負面影響。同樣，如果某人的申請在過去被批準過，則該批準可能會增加此人當前申請獲得批準的機會。通常情況下，歷史數據庫將有數百萬行，因此我們需要一個精心設計的解決方案來匹配歷史數據庫中的新申請人。

假設數據庫中的歷史表如下所示：

在此表中，第一列Personal ID與歷史數據庫中每個唯一的申請人相關聯。如果歷史數據庫中有3000萬個唯一的申請人，那么將有3000萬個唯一的Personal ID。每個Personal ID都在歷史數據庫系統中標識一個申請者。

第二列是Application ID，每個Application ID都標識了系統中唯一的申請。一個人可能在過去申請過不止一次，因此，這意味著在歷史數據庫中我們所擁有的不同的Application ID會比Personal ID多。如上表所示，John Doe只有一個Personal ID，卻有兩個Application ID。

上表只顯示了歷史數據集的一個樣本。假設歷史數據集有近100萬行，其中包含了過去10年的申請人記錄。新的申請人以平均每分鐘約2個申請人的速度不斷到來。對于每個申請人，我們需要完成以下工作：

• 為申請人發放新的Application ID。
• 查看歷史數據庫中是否有匹配的申請人。
• 如果找到了匹配的申請人，則使用歷史數據庫中找到的該申請人的Personal ID。我們還需要確定歷史數據庫中已批準或拒絕該申請人的次數。
• 如果沒有找到匹配的申請人，那么我們需要為這個人發放新的Personal ID。

假設一個申請人帶著以下憑證來到這里：

• First name: John
• Surname: Doe
• DOB: 2000-09-19

現在，我們如何設計一個查找成本低的高效應用呢？

在數據庫中搜索新的申請人的一種策略可以設計如下：

• 按照DOB（出生日期）對歷史數據庫進行排序。
• 每次有申請人到達時，向申請人發放新的申請ID。
• 取出所有符合該出生日期的記錄，這將是主要的查找過程。
• 在匹配的記錄中，使用名字（First name）和姓氏（Surname）進行二次查找。
• 如果找到匹配的申請人，則用Personal ID來指代該申請人，計算該申請人被批準和拒絕的次數。
• 如果沒有找到匹配項，則向該申請人發放新的Personal ID。

我們嘗試選擇合適的算法對歷史數據庫進行排序。我們可以放心地排除冒泡排序，因為數據量很大。希爾排序有更好的表現，但前提是列表已經部分排好序。因此，歸并排序可能是對歷史數據庫進行排序的最佳選擇。

當一個申請人到來時，我們需要在歷史數據庫中定位并查找這個人。由于數據已經進行了排序，因此可以使用插值查找或二分查找。由于是按照DOB（出生日期）進行排序的，申請人很可能會均勻分布，所以我們可以放心地使用插值查找。

我們先基于DOB（出生日期）進行查找，返回一組具有相同出生日期的申請人。現在，需要在具有相同出生日期的一小部分人中找到所需的人。由于我們已經成功地將數據縮小為一個小的子集，因此可以使用任何查找算法（包括線性查找）來查找申請人。請注意，我們在這里稍微簡化了二次查找問題。如果找到多個匹配項，我們還需要通過匯總查找結果來計算被批準和拒絕的總數。

在現實世界中，由于名字和姓氏的拼寫可能略有不同，因此在二次查找中需要使用某種模糊搜索算法來識別每個人。查找中可能需要使用某種距離算法來實現模糊查找，比如相似度超過規定閾值的數據點將被認為是同一個人。