An exhaustive, representative test database in phrase search algorithm
Based on the example I assume that the target is persons names. 

Let's be clear, there's no such thing as an exhaustive dataset containing all possible persons names in the world. Also a crucial part of the question is: in What kind of names? In which language? Persons names in English are pretty different from names in Chinese for instance. And there is also the difficult question of transliteration of proper names.

That being said, a few resources exist. They would usually be found by searching resources for "personal names", "record linkage", "named entities matching/coresolution". The following ones probably don't cover all the requirements but it's a start:


Febrl (see also here) 
Found This paper which presents a large resource and this corresponding resource description but couldn't find the data.
The EMM news explorer has an interesting database of named entities including persons names with all the spelling variants/transliterations.