I'm trying to categorize file names of anime episodes (for now) into appropriate title based categories. The Show-titles are parsed from an XML file (I got from Anime News Network).
EDIT: The passed on backgroundWorker
object type variable is just to facilitate GUI update as this algorithm runs on a secondary thread.
DESCRIPTION: The algorithm itself is pretty straightforward, it finds matches for each keyword in the file name with a set list of show-titles and assigns a score corresponding to the show-title. After all the keywords are checked for matches, the show-title with the highest score is given as the category
to the file.
There are a few tweaks to boost the score in certain cases as well, like if the directory names match with the same show-title and if the score and the show-title length are almost the same number.
ADDITION: Class level variable declarations for context
OpenDialogView openDialog;
List<DirectoryInfo> dirList;
BackgroundWorker AnalyzerThread;
// Analyzer Components
public static char[] removablesNum = new char[] { '.', '_', '-', ' ', '^', '!', '@', '#', '$', '%', '&', '*', '~', '`', '?', '(', ')', '[', ']', '{', '}', '+', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };
public static char[] removables = new char[] { '.', '_', '-', ' ', '^', '!', '@', '#', '$', '%', '&', '*', '~', '`', '?', '(', ')', '[', ']', '{', '}', '+' };
public static string animeDBPath = "ANN_AnimeDB_20-12-2015.xml";
public string parentPath, outputPath;
public List<string> titles;
public List<Children> notSortedFiles;
public List<Category> sortedFiles;
CODE:
#region Analyzer
private void RunAnalysis(object backgroundWorker)
{
titles = LoadXML(animeDBPath, "item", "name");
List<DirectoryInfo> dirs = new List<DirectoryInfo>();
List<FileInfo> allFiles = new List<FileInfo>();
// Find all directories
foreach (DirectoryInfo d in dirList)
{
dirs.AddRange(d.GetDirectories("*", SearchOption.AllDirectories));
}
// Add the parent directory as well
dirs.AddRange(dirList);
// Find all the files
foreach (DirectoryInfo dir in dirs)
{
allFiles.AddRange(dir.EnumerateFiles());
}
sortedFiles = SortFiles(allFiles, backgroundWorker);
}
private List<Category> SortFiles(List<FileInfo> allFiles, object backgroundWorker)
{
List<Category> categories = new List<Category>();
int fileCount = 0;
foreach (FileInfo file in allFiles)
{
fileCount++;
string[] subStrings = file.Name.Split(removables, StringSplitOptions.RemoveEmptyEntries);
// score holds a value for each title, highest score indicates closer match
int[] score = new int[titles.Count];
bool hasAScore = false;
// list's length - 1 to avoid extensions from being checked
for (int i = 0; i < titles.Count; i++)
{
for (int j = 0; j < subStrings.Length - 1; j++)
{
// @\b defines the match to be specific to whole words
if (Regex.IsMatch(titles[i], @"\b" + subStrings[j] + @"\b", RegexOptions.IgnoreCase))
{
// If a match is found, check the directory paths to enforce the match
foreach (string s in file.Directory.Name.Split(removables, StringSplitOptions.RemoveEmptyEntries))
{
if (Regex.IsMatch(titles[i], @"\b" + s + @"\b", RegexOptions.IgnoreCase))
{
score[i]++;
}
}
score[i]++;
hasAScore = true;
// Console.WriteLine("Found match with title '{0}' with string '{1}' from file '{2}'", titles[j], subStrings[i], file.Name);
}
}
// if the percentage of word matches and total words in the title is > 80% (arbitrary)
// To avoid false matches with longer titles
// boost the score
int titleWordCount = titles[i].Split(removables, StringSplitOptions.RemoveEmptyEntries).Length;
if ((100 * (score[i]) / (2 * titleWordCount)) > 80)
{
score[i] += 2;
}
}
if (hasAScore)
{
// Find the highest score in the list and use it's title value as the title of the Category
string titleName = titles[Array.IndexOf(score, score.Max())];
bool exists = false;
// Check through all the categories if it already exists, otherwise add a new one
// TODO perhaps check this in the class's constructor
foreach (Category c in categories)
{
if (c.Name == titleName)
{
c.AddChildren(new Children(file), titleName);
exists = true;
break;
}
}
if (!exists)
{
categories.Add(new Category(new Children(file), titleName));
}
}
else
{
// Files without a score were not matched with any existing category
notSortedFiles.Add(new Children(file));
}
// Console.WriteLine("File: '{0}' has a max score of {1}", file.Name, score.Max());
// Update Progress
// Send percentComplete to the backgroundWorker and the current file number
int progressPercentage = 100 * fileCount / allFiles.Count;
// Only the ReportProgress method can update the UI
(backgroundWorker as BackgroundWorker).ReportProgress(progressPercentage, fileCount);
}
return categories;
}
private List<string> LoadXML(string filePath, string descendant, string element)
{
// Load the db
XDocument db = XDocument.Load(@filePath);
List<string> titles = new List<string>();
var query = from c in db.Root.Descendants(descendant)
// Only do anime
select c.Element("type").Value == "TV" ? c.Element(element).Value : "null";
foreach (string animeName in query)
{
titles.Add(animeName);
}
// Sanitize "null" additions
titles.RemoveAll(value => value == "null");
titles.Sort();
titles = DeAccentTitles(titles);
return titles;
}
private List<string> DeAccentTitles(List<string> titlesToClean)
{
List<string> sanitizedTitles = new List<string>();
foreach (string s in titlesToClean)
{
string nfdNormalizedString = s.Normalize(NormalizationForm.FormD);
StringBuilder builder = new StringBuilder();
foreach (char c in nfdNormalizedString)
{
if(CharUnicodeInfo.GetUnicodeCategory(c) != UnicodeCategory.NonSpacingMark)
{
builder.Append(c);
}
}
sanitizedTitles.Add(builder.ToString().Normalize(NormalizationForm.FormC));
}
return sanitizedTitles;
}
#endregion
Sample File names:
ShingekinoKyojinOVA-01(480p)[Hatsuyuki-Kaitou][D8E8CC75].mkv -- Expected Category "Shingeki no Kyojin"
(Hi10)_Gosick_-_22_The_Christmas_Carol_Adorns_the_Happiness_by_the_Window_(BD_720p)_(Broken).mkv -- Expected Category "Gosick"
Manyuu.Hiken-chou.04.HD.BD.Kira.ACB.mkv -- Expected Category "Manyu Hiken-cho"
Commie_Steins Gate 01 Prologue to the Beginning and End.mkv -- Expected Category "Steins Gate"
Commie_Steins_Gate_02_BD_720p_AnimeKens.com.mkv -- Expected Category "Steins Gate"
Extract from the Source XML File:
<report>
<args>
<type>anime</type>
<name></name>
<search></search>
</args>
<item>
<id>17938</id>
<gid>721551383</gid>
<type>ONA</type>
<name>Koyomimonogatari</name>
<precision>ONA</precision>
<vintage>2016-01-09</vintage>
</item>
<item>
<id>17937</id>
<gid>1319318627</gid>
<type>TV</type>
<name>Qualidea Code</name>
<precision>TV</precision>
</item>
</report>
I have a related question on SO regarding the approach to this kind of categorization problem (if you need more context).
EDIT: My code runs fine but as mentioned above, produces surprising false-positives. It's also quite slow, that's why I'm looking for a code review to improve it's performance and possibly realize the cause of the false-positives.
By the way, since this is a statistical algorithm, a few wrong results doesn't mean it's not working. It's working to an acceptable standard and improving correct prediction rate is not the primary concern.