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;
	}
}