Mathematik & Algorithmen

Statistik

Benfordsches Gesetz

Das Benfordsches Gesetz sagt etwas über die Wahrscheinlichkeit des Auftretens der verschiedenen Ziffern an der n. Stelle einer Zahl in empirischen Datensätzen aus. Beispielsweise ist es viel wahrscheinlicher, dass eine Zahl mit einer 1 beginnt, als dass eine Zahl mit 9 beginnt.
Anwendungsbeispiele sind z.B. der Nachweis von Manipulationen bei Wahlen oder Abrechnungen.

German tank problem

Das http://en.wikipedia.org/wiki/German_tank_problem behandelt das Problem, dass man eine unbekannte Anzahl (N) an produzierten Einheiten hat, die alle eine aufsteigende Seriennummer aufgedruckt haben. Man nimmt dann eine bestimmte Anzahl (k) an Stichproben und ermittelt von allen Stichproben die höchste Seriennummer (m).

Dann erhält man so eine ziemlich gute Schätzung für die höchste Seriennummer (die der Anzahl der produzierten Einheiten entspricht):

N = m + m/k - 1

Anwendung, z.B. wieviele Panzer wurden produziert.

Die Levenshtein Distanz

Man hat zwei Zeichenketten, z.B. "Affe" und "Apfel" und möchte ein Maß dafür erhalten, wie ähnlich sich die beiden Zeichenketten sind. Die Levenshtein Distanz liefert die minimale Anzahl an Einfüge-, Lösch- und Ersetzoperationen, um die erste Zeichenkette in die zweite umzuwandeln. Man könnte z.B. mit einer Ersetzung und einer Einfügeoperation "Affe" in "Apfel" umwandeln. Falls beide Operationen mit 1 bewertet würden wäre die Distanz der beiden Zeichenketten dann 2.

• Wikipedia Levenshtein Distanz
• Wikibooks Implementierung der Levenshtein Distanz

Hier ist ein Beispiel für eine Implementierung der Distanz in Java

/** 
 * 

 *   http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance
 
 */
public class LevenshteinDistance
{
   private String string1;
   private String string2;
   private int[][] distMatrix;
	
    private int costAdd=1;
    private int costReplace=1;
    private int costRemove=1;

    /**
     * @param pValA int value 1
     * @param pValB int value 2
     * @param pValC int value 3
     * @return the minumum of int value 1-3
     */
    private static int getMinimumOfThree(int pValA, int pValB, int pValC)
    {
    	int lMin;
    	lMin=Math.min(pValA, pValB);
    	lMin=Math.min(lMin, pValC);
    	return lMin;
    }

    /**
     * Constructor to get an object to get the Levenshtein distance betweent string 1 and string 2
     * @param pString1     String 1
     * @param pString2     String 2
     * @param pCostAdd     Cost for adding    a char to string 1 to match string 2
     * @param pCostReplace Cost for replacing a char to string 1 to match string 2
     * @param pCostRemove  Cost for removing  a char to string 1 to match string 2
     */
    public LevenshteinDistance(String pString1, String pString2, int pCostAdd, int pCostReplace, int pCostRemove)
    {
    	this(pString1, pString2);

    	if(pCostAdd<0 || pCostReplace <0 || pCostRemove<0) throw new IllegalArgumentException("Negative costs are not allowed");
    	costAdd=pCostAdd;
    	costReplace=pCostReplace;
    	costRemove=pCostRemove;    	
    }
    
    /**
     * Constructor to get an object to get the Levenshtein distance betweent string 1 and string 2
     * All costs are set to default value 1
     * @param pString1     String 1
     * @param pString2     String 2
     */
    public LevenshteinDistance(String pString1, String pString2)
    {
    	string1=pString1;
    	string2=pString2;    	
    }
    
    /**
     * @return String 1
     */
    public String getString1()
    {
	return string1;
    }

    /**
     * @return String 2
     */
    public String getString2() {
        return string2;
    }

    /**
     * @return The Levenshtein distance matrix
     */
    private int[][] getDistanceMatrix()
    {
        if(distMatrix==null)
        {
            distMatrix=this.computeLevenshteinDistance();
        }
        return distMatrix;
    }
    
    /**
     * @return What is the minimum distance between string 1 and string 2
     */
    public int getMinDistance()
    {
        int result=this.getDistanceMatrix()[string1.length()][string2.length()];
        return result;
    }
    
    /**
     * @return Show one way to change string 1 into string 2 with the minimum amount of operations
     */
    public String getOperations()
    {
        return findOperationsRec(string1.length(), string2.length());
    }
    
    /**
     * Find one way to change string 1 into string 2 starting from i,j
     * @param i position in string 1
     * @param j position in string 2
     * @return String with operations 
     */
    private String findOperationsRec(int i, int j)
    {        
        int left=(i<=0)         ? -1 : getDistanceMatrix()[i-1][j];
        int top= (j<=0)         ? -1 : getDistanceMatrix()[i][j-1];
        int here=getDistanceMatrix()[i][j];
        int diag=(i<=0 || j<=0) ? -1 :getDistanceMatrix()[i-1][j-1];
    
        // a removal?
        if (i>0 && (left) + costRemove == here)
        {
            return  findOperationsRec(i-1, j)+'-';
        }
        
        // an addition?
        if(j>0 && top + costAdd == here)
        {
            return findOperationsRec(i, j-1)+'+';

        }
        
        // a replacement?
        if(i>0 && j>0 && diag + costReplace == here)
        {
            return findOperationsRec(i-1, j-1)+'r';
        }
        
        // if non of the other cases applied, it must have been equal
        if(i>0 && j>0 && diag  == here)
        {
            return findOperationsRec(i-1, j-1)+'=';
        }
        return "";
    }
          
    /**
     * @return return the calculated Levenshtein distance matrix for string 1 to string 2
     */
    private synchronized int[][] computeLevenshteinDistance()
        {
         int[][] distance = new int[string1.length() + 1][string2.length() + 1];

         for (int i = 0; i <= string1.length(); i++)
         {
            distance[i][0] = i;
         }
        
         for (int j = 0; j <= string2.length(); j++)
         {
            distance[0][j] = j;
         }

         for (int i = 1; i <= string1.length(); i++)
         {
            for (int j = 1; j <= string2.length(); j++)
            {
                int a=distance[i - 1][j] + costRemove;
                int b=distance[i][j - 1] + costAdd;
                int c=distance[i - 1][j - 1];
                if(string1.charAt(i - 1)!=string2.charAt(j - 1))
                {
                    c=c+costReplace;
                }
                distance[i][j] = getMinimumOfThree(a, b, c);
            }
         }
         return distance;
     }

    @Override
    public String toString()
    {
        StringBuffer result=new StringBuffer();
        result.append(string1);
        result.append("\n");
        result.append(string2);
        result.append("\n");
        
        int maxNr=0;
        for (int i = 1; i <= string1.length(); i++)
        {
            for (int j = 1; j <= string2.length(); j++)
            {
                int distval=getDistanceMatrix()[i-1][j-1];
                if(maxNr<distval) maxNr=distval;
            }
        }
        
        for (int i = 1; i <= string1.length(); i++)
        {
            for (int j = 1; j <= string2.length(); j++)
            {
                int distval=getDistanceMatrix()[i-1][j-1];
                String distvalString=String.valueOf(distval);
    
                                while(distvalString.length()<String.valueOf(maxNr).length())
                {
                    distvalString=" "+distvalString;
                }
                result.append(distvalString);
                result.append(" ");
            }
            result.append("\n");
        }
        result.append("Min Distance:");
        result.append(this.getMinDistance());
        result.append("\n");
        result.append("Schritte: ");
        result.append(this.getOperations());
        result.append("\n");
        return result.toString();
    }
    
}

Und mit diesem Komparator kann in Java eine Liste von Strings danach sortiert werden, wie ähnlich sie einem vorgegeben String sind.

import java.util.Comparator;

/**
 * Compares two strings vs a reference string. This will tell you
 * which of the two strings is more similar to reference string
 *
 */
public class LevenshteinDistanceComparator implements Comparator<String>
{
	String referenceString;
	private int costAdd=1;
	private int costReplace=1;
	private int costRemove=1;

	/**
	 * @param pReferenceString The reference string
	 */
	public LevenshteinDistanceComparator(String pReferenceString)
	{
		referenceString=pReferenceString;
	}

	/**
	 * @param pReferenceString The reference string
	 * @param pCostAdd         How expensive should it be if we need to add a character
	 * @param pCostReplace     How expensive should it be if we need to replace a character
	 * @param pCostRemove      How expensive should it be if we need to remove a character
	 */
	public LevenshteinDistanceComparator(String pReferenceString, int pCostAdd, int pCostReplace, int pCostRemove)
	{
		this(pReferenceString);
		costAdd=pCostAdd;
		costReplace=pCostReplace;
		costRemove=pCostRemove;
	}

	/**
	 * @param pReferenceString The reference string
	 */
	private int getLevenshteinDistance(String pString)
	{
		LevenshteinDistance lev=new LevenshteinDistance(referenceString, pString, costAdd, costReplace, costRemove);
		int distance=lev.getMinDistance();
		return distance;
	}
	
	/* (non-Javadoc)
	 * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
	 */
	@Override
	public int compare(String o1, String o2)
	{
		if(o1==null || o2==null) throw new NullPointerException("Can not compare null strings");
		
		Integer dist1=getLevenshteinDistance(o1);
		Integer dist2=getLevenshteinDistance(o2);
		return dist1.compareTo(dist2);
	}

}