Tölvunarfræði 2 - Vor 2012


Aukaverkefni 4 - Sýnislausn


Lausnum skal skilað til viðkomandi dæmakennara (sjá lista yfir dæmatíma).

Reynið að skrifa stutt, skýr og hnitmiðuð forrit. Notið réttan inndrátt og gætið þess að forritin ykkar séu læsileg.

Skiladagur: þriðjudaginn 17. apríl fyrir kl 16:00


Aukaverkefni (10 stig) - Algengustu gildi í endalausum straumi


Gefum okkur að við séum með endalausan straum af gildum. Við getum byrjað að lesa strauminn á tilteknum tímapunkti en hann hættir aldrei. Slíkur straumur gæti til dæmis innihaldið fyrirspurnir á Google leitarvélina, Twitter skilaboð, o.s.frv.

Okkur langar til að vita K algengustu gildin (top K) í straumnum á hverjum tímapunkti í lestrinum.

Til að flækja málin þá skulum við gera ráð fyrir því að það séu svo mörg mismunandi gildi í straumnum að einföld talning með hakkatöflu er útilokuð því við höfum ekki pláss fyrir öll gildin. En á móti skulum við gera ráð fyrir að talningin þurfi ekki að vera alveg nákvæm -- við erum tilbúin að sætta okkur við skekkjur (en ætlum ekki að fara neitt nákvæmlega út í hversu mikla skekkju.)

Til að leysa verkefnið þá skuluð þið útfæra einfalda útgáfu af s.k. Count Min Sketch (CM) (gagnamót fyrir líkindafræðilega samantekt á gildum). Þið getið notað CM gagnamótið til að halda utan um tíðni gilda (innan vissra skekkjumarka).

Til að halda utan um top K gildin á hverjum tíma þá skuluð þið nota hrúgu með K gildum. Þegar nýtt gildi kemur inn þá er því bætt inn í CM gagnamótið, tíðni þess gildi er athuguð og ef hún er hærri en lægsta top K gildisins í hrúgunni og gildið er ekki þegar í hrúgunni þá skiptið þið minnsta gildinu út (og þurfið að koma hrúgunni á rétt form aftur), en ef gildið er þegar í hrúgunni þá uppfærið þið tíðni þess og lagfærið hrúguna.

Útfærslan á CM sketch byggir á sambærilegri hugmynd og svokallaðir Bloom filters. Bæði gagnamótin hafa það sameiginlegt að þurfa safn af H tætiföllum og útfærsla þeirra er það flóknasta í útfærslunni á bloom filters og CM.


Prófun


Við skulum nota mobydick.txt til að prófa forritið. Það eru 22158 orð í henni. Við ætlum að finna topp 10 orðin í mobydick.txt.

Tíu algengustu orðin í mobydick.txt eru:

hhg@hhg:~/t2/V13a$ grep -o -E '\w+' mobydick.txt | sort | uniq -c | sort -n -k 1 | tail -n 10
   2098 I
   2183 it
   2438 his
   2945 that
   3842 in
   4474 to
   4487 a
   5951 and
   6432 of
  13555 the
hhg@hhg:~/t2/V13a$ 

TopK forritið skilar okkur eftirfarandi nálgun:

hhg@hhg:~/t2/V13a$ java TopK < mobydick.txt | sort -n -k 1
    1979 as
    2029 I
    2692 his
    2968 that
    4129 in
    4631 to
    4747 a
    6061 and
    6692 of
   13839 the
hhg@hhg:~/t2/V13a$ 

Lausn


Lausn - TopK.java


import java.util.Scanner;

public class TopK
{
	private CountMin cm;
	private TopHeap heap;
	private int k;

	public TopK(int k)
	{
		this.cm = new CountMin(0.01, 0.01);
		this.heap = new TopHeap(k);
		this.k = k;
	}

	public void add(String s)
	{
		cm.add(s);

		if (heap.contains(s))
		{
			heap.increaseWeight(s, 1);
			return;
		}

		if (heap.count() < k)
		{
			heap.put(s, 1);
			return;
		}

		int n = cm.getEstimate(s);
		int worst = heap.peek();

		if (n < worst)
			return;

		heap.replaceSmallest(s, n);
	}

	public int count(String key)
	{
		return cm.getEstimate(key);
	}

	public Iterable<String> keys()
	{
		return heap.keys();
	}

	public static void main(String[] args)
	{
		Scanner scan = new Scanner(System.in);

		TopK top = new TopK(10);

		while (scan.hasNext())
		{
			String word = scan.next();

			top.add(word);
		}

		for (String s : top.keys())
		{
			System.out.printf("%8d %s\n", top.count(s), s);
		}
	}
}

TopHeap.java


import java.util.HashMap;
import java.util.LinkedList;

class TopHeap
{
	// Gildin eru í f[0..n-1] í hrúgu með minnstu
	// þyngd efst (samkvæmt weight)
	//
	// Með öðrum orðum, þá gildir eftirfarandi
	// röð um hrúguna:
	//   f[i].weight < f[2*i+1].weight
	//   f[i].weight < f[2*i+2].weight
	//
	// Gildin eru einnig öll í map.

	private Element[] f;
	private HashMap<String, Element> map;
	private int n;

	public static class Element
	{
		String value;
		int weight;
		int position;
	}

	public TopHeap(int max)
	{
		this.n = 0;
		this.f = new Element[max];
		this.map = new HashMap<String, Element>();
	}

	public void increaseWeight(String key, int w)
	{
		Element e = map.get(key);
		e.weight += w;
		fixHeap(e.position);
	}

	public boolean contains(String key)
	{
		return map.containsKey(key);
	}

	public int peek()
	{
		return f[0].weight;
	}

	public void put(String s, int w)
	{
		Element e = new Element();

		e.value = s;
		e.weight = w;
		e.position = n;

		f[n++] = e;

		map.put(s, e);

		fixHeapUp(n-1);
	}

	public void replaceSmallest(String key, int w)
	{
		Element smallest = f[0];

		map.remove(smallest.value);

		smallest.value = key;
		smallest.weight = w;

		map.put(key, smallest);

		fixHeapDown(0);
	}

	public int count()
	{
		return n;
	}

	public Iterable<String> keys()
	{
		LinkedList<String> q = new LinkedList<String>();

		for (int i = 0; i < n; i++)
			q.add(f[i].value);

		return q;
	}

	private static void swap(Element[] f, int a, int b)
	{
		Element tmp = f[a];
		f[a] = f[b];
		f[b] = tmp;
		f[a].position = a;
		f[b].position = b;
	}

	private void fixHeap(int i)
	{
		if (i != 0 && f[i].weight < f[(i-1)/2].weight)
			fixHeapUp(i);
		else
			fixHeapDown(i);
	}

	private void fixHeapUp(int i)
	{
		while (i > 0)
		{
			// f[0..n-1] er í hrúgu nema e.t.v.
			// er f[i] of neðarlega.

			int parent = (i-1)/2;

			if (f[parent].weight <= f[i].weight)
				break;

			// f[i] < f[parent], þ.e. barn er minna
			// en foreldri og þurfum því að víxla þeim

			swap(f, i, parent);
			i = parent;
		}
	}

	private void fixHeapDown(int i)
	{
		while (true)
		{
			// f[0..n-1] er hrúga nema e.t.v.
			// er f[i] of ofarlega.
			// 0 <= i <= n

			int b = 2*i+1;

			if (b >= n) return; // f[i] er barnlaust (lauf)

			if (b+1 < n && f[b+1].weight < f[b].weight)
				// Veljum hægra barnið ef það er minna en vinstra
				b++;

			if (f[i].weight <= f[b].weight)
				// f[i] er á réttum stað
				return;

			// f[b] < f[i], þ.e. foreldri er stærra
			// en barn og þurfum því að víxla þeim.

			swap(f, i, b);

			i = b;
		}
	}

}

CountMin.java


import java.security.MessageDigest;

public class CountMin
{
	private static MessageDigest md;
	private int width;
	private int depth;
	private int[][] count;

	static
	{
		try
		{
			md = MessageDigest.getInstance("SHA-1");
		}
		catch (Exception e)
		{
			md = null;
		}
	}

	public CountMin(double eps, double delta)
	{
		this.width = (int) Math.ceil(Math.E / eps);
		this.depth = (int) Math.ceil(Math.log(1.0/delta));

		count = new int[depth][width];
	}

	public void add(String s)
	{
		int[] h = hash(s, depth);

		for (int i = 0; i < depth; i++)
		{
			int p = (h[i] & 0x7fffffff) % width;

			count[i][p]++;
		}
	}

	public int getEstimate(String s)
	{
		int[] h = hash(s, depth);

		int p = (h[0] & 0x7fffffff) % width;
		int min = count[0][p];

		for (int i = 1; i < depth; i++)
		{
			p = (h[i] & 0x7fffffff) % width;

			if (count[i][p] < min)
				min = count[i][p];
		}

		return min;
	}

	private static int[] hash(String s, int h)
	{
		int[] result = new int[h];
		byte[] data = s.getBytes();

		int k = 0;
		byte salt = 0;

		while (k < h)
		{
			byte[] digest;

			md.update(salt);
			salt++;

			digest = md.digest(data);

			int i = 0;

			while (i < digest.length && k < h)
			{
				result[k] = ((int)digest[i+3] & 0xff) | ((digest[i+2] & 0xff) << 8) | ((digest[i+1] & 0xff) << 16) | ((digest[i] & 0xff) << 24);
				k++;
				i += 4;
			}
		}

		return result;
	}
}