In English

Java exception matching in real time using fuzzy logic

Karl Tillström
Göteborg : Chalmers tekniska högskola, 2010. 58 s.
[Examensarbete på avancerad nivå]

This thesis deals with the problem of matching Java exceptions that originates from the same problem, but looks a bit dissimilar. The matching must be done within reasonable time to be able to be carried out automatically. Different ways of utilizing fuzzy string matching logic is examined in general and how to apply it to Java exceptions specifically. The exceptions are divided into separate logical parts and the analysis deals with how to weight the importance of the parts and application of fuzzy matching between them. Java exceptions can be linked in "caused by" chains depending on where they occur and what effects they have. In short - an exception can cause other exceptions to occur, and thus the first exception is a "caused by exception" to the second one. In this thesis the resulting algorithm groups exceptions together with their "caused by":s and compares the top and bottom exceptions of the chain with other top and bottom exceptions to find matches. To determine degree of similarity a number of fuzzy string matching algorithms where examined including "Levenshtein", "Damerau-Levenshtein", "Needleman-Wunch", "Jaro-Winkler", "Bitap", "Boyer-Moore" and in some degree "Ukkonen". In the end, a modified version of the original Levenshtein algorithm - utilizing lazy evaluation and thresholding - was determined the best suited comparison algorithm for this problem.

Sammanfattning
Den här examenstesen berör problemet om att matcha avbrott i Java (eng: exceptions) som härrör från samma problem, men av olika anledningar ser lite olika ut. Matchningen måste göras inom rimlig tid för att kunna användas automatiskt av andra applikationer i realtid. För att lösa detta undersöks olika sätt att applicera s.k. fuzzy string matchingalgoritmer på Java-avbrott. Java-avbrott är uppdelade i olika logiska delar och analysen handlar om hur man kan vikta hur viktiga de olika delarna är och hur fuzzy string matching kan användas för att få fram likheter. Java-avbrott kan även vara ihoplänkade i orsaks-kedjor (eng: caused by) beroende på var de uppstår och vilka effekter de har. Kortfattat kan ett avbrott orsaka att ett annat uppstår och då blir det första avbrottet ett orsaksavbrott till det andra. I den här tesen grupperas avbrott ihop med deras orsakande avbrott och det översta i kedjan sätts ihop med det understa och jämförs med andra topp- och bottenavbrott. För att avgöra graden av likhet mellan de olika delarna har ett antal "fuzzy string matching"-algoritmer jämf örts: "Levenshtein", "Damerau-Levenshtein", "Needleman-Wunch", "Jaro- Winkler", "Bitap", "Boyer-Moore" och i viss mån "Ukkonen". Slutligen har en modifierad variant av Levenshteinalgoritmen visats vara bäst lämpad för det här problemet - en Levenshtein med modifikationen att den anv änder "Lazy evaluation" samt ett tröskelvärde för hur olika strängar får vara som mest innan de kastas bort.



Publikationen registrerades 2010-06-03. Den ändrades senast 2013-04-04

CPL ID: 122239

Detta är en tjänst från Chalmers bibliotek