Clustering algorithm to sort filenames A client would like to sort out his filesystem (~ 1,000,000,000 files), which has been fed by numerous workers over the years, each with their own unknown naming convention, e.g.:


[DATE]-[CLIENT]-[FILENAME]
[TYPE]-[CLIENT].[DATE][FILENAME]
...


Here are four examples (out of ~1,000,000,000 files) to make things clearer:

JPM_TPD0001662_2009124012302000451.pdf

JPMF_STA_1712010832_18001_LUX_approval.pdf

CHACN05CTRP_00111.001.pdf

CHACN63CJO1_00018.001.pdf

The purpose is to find out patterns in the naming conventions, but I can't use regular expressions, since the conventions are unknown a priori.

I was wondering whether there was a kind of clustering algorithm to be able to group files according to their naming conventions.

Any K-Mean philosophy applied to strings?
This is not at all a typical clustering problem, so I doubt any of these algorithms will help. If you want to try clustering, you will need to do appropriate feature extraction. Don't expect things to work on the raw data. But I guess once you have good features, the problem will already be solved.

Instead of trying to frame this as a clustering problem, look at it either from a sequential pattern view point, or even better: look at the few questions on how to learn regexps from a set of strings.