You can use Solr's Fuzzy Search for this, you have to scroll down a bit on the page.
Solr's standard query parser supports fuzzy searches based on the Levenshtein Distance or Edit Distance algorithm. Fuzzy searches discover terms that are similar to a specified term without necessarily being an exact match. To perform a fuzzy search, use the tilde ~ symbol at the end of a single-word term.
Assuming you have a schema like below, where this field phash
holds the phash you have calculated.
<fields>
<!-- ... all your other fields ... -->
<field name="phash" type="string" indexed="true" stored="true" />
</fields>
You may perform a query like
q=phash:004143737f7f7f7f~0.8&
fl=score,phash
This will return all documents that have a PHASH with a Levenshtein Distance or Edit Distance
of at least 80%. You will not get the 95.3125% you have given in your question, but a 87,5% as matching/not matching characters are counted.
When you want to see that value, you may perform the following query
q=phash:004143737f7f7f7f~0.8&
fl=score,phash,strdist("0041417f7f7f7f7f", phash, edit)
This is a function call to fetch the String Distance using the Levenstein or Edit distance and will deliver a result similar to
+----------------+---------------------------------------+
|hash |strdist("0041417f7f7f7f7f", hash, edit)|
+----------------+---------------------------------------+
|0041417f7f7f7f7f|1.0 |
+----------------+---------------------------------------+
|004143737f7f7f7f|0.875 |
+----------------+---------------------------------------+
When you want to reduce the gap between 95.3125%
and 87,5%
you should consider to store the PHASH not as hexadecimal value, but as octal for instance.