'자바'에 해당되는 글 3건

  1. 2012.02.09 [알고리즘] 카프-라빈 알고리즘 구현해보기 (2)
  2. 2012.02.06 [JAVA] txt 파일 입출력 관련 팁 - 인코딩(encode) (1)
  3. 2011.10.30 [자료구조] 자바로 만든 큐(Queue) (1)
2012.02.09 18:06
카프-라빈 알고리즘?

  카프-라빈 알고리즘은 문자열내에서 특정 문자열을 검색하는데 사용되는 알고리즘 중 하나입니다.
  자세한 내용은 링크 참초 -> http://carstart.tistory.com/97

소스코드

import java.util.ArrayList;

public class SearchTest {

	public static void main(String[] args) {
		String ori = "한글/헬로월드asd123asd한글을 찾아봐ㅋㅋㅋ";
		String word = "한글";
		
		int index = Searcher.KR_SearchOnce(ori, word);
		System.out.println("where? : index " + index);

		if (index == -1) {
			System.out.println("not found!");
		} else {
			System.out.println("found! : " + ori.substring(index, index + word.length()));
		}

		int[] index2 = Searcher.KR_SearchAll(ori, word);

		for (int i = 0; i < index2.length; i++) {
			System.out.println(index2[i]);
		}
	}
}

class Searcher {
	private final static int Q = 2111;

	// true == 대소문자 구분
	public static int[] KR_SearchAll(String ori, String s, boolean charsCase) {
		if (charsCase) {
			return KR_SearchAll(ori, s);
		} else {
			return KR_SearchAll(ori.toUpperCase(), s.toUpperCase());
		}
	}

	public static int[] KR_SearchAll(String ori, String s) {
		if (KR_SearchOnce(ori, s) == -1) return null;

		ArrayList<Integer> result = new ArrayList<Integer>();

		String mori = ori.concat("");
		int index = 0;
		int in = 0;

		in = KR_SearchOnce(mori, s);
		index += in;
		mori = ori.substring(index + s.length());
		result.add(index);

		lb: while (true) {
			in = KR_SearchOnce(mori, s);
			index += in + s.length();
			if (in == -1) break lb;
			mori = ori.substring(index + s.length());
			result.add(index);
		}

		int[] r = new int[result.size()];
		for (int i = 0; i < result.size(); i++) {
			r[i] = result.get(i);
		}

		return r;
	}

	public static int KR_SearchOnce(String ori, String s) {
		long ss = getHash(s);
		long H = 0;
		int m = s.length();

		if (ori.length() < m) return -1;

		H = getHash(ori.substring(0, s.length()));
		if (ss == H) return 0;

		char c, cc;

		for (int i = 1; i <= ori.length() - m; i++) {
			c = ori.charAt(i - 1);
			cc = ori.charAt(i + m - 1);
			// H = (long) (2 * (H - c * Math.pow(2, m - 1)) + cc) % Q;
			H = (long) (2 * (H - c * Math.pow(2, m - 1)) + cc);
			if (ss == H) {
				if (s.equals(ori.substring(i, i + m))) {
					return i;
				}
			}
		}
		return -1;
	}

	public static long getHash(String data) {
		int l = data.length();
		long ldata = 0;
		char c;

		for (int i = 0; i < l; i++) {
			c = data.charAt(l - i - 1);
			ldata += c * Math.pow(2, i);
		}
		// return ldata %= Q;
		return ldata;
	}
}


 
실행 결과 :  

where? : index 0

found! : 한글

0

16



아...뭔가 찝찝하게..구현해 논것 같지만;; 작동은 하니....
저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License

'Math/Pahycis/Algorithm' 카테고리의 다른 글

[알고리즘] 카프-라빈 알고리즘 구현해보기  (2) 2012.02.09
Shortest Path Algorithm  (1) 2011.12.05
Voronoi diagram  (1) 2011.12.05
Trackback 0 Comment 2
  1. 2012.02.10 10:53 address edit & del reply

    비밀댓글입니다

  2. 2012.02.10 10:55 address edit & del reply

    비밀댓글입니다

2012.02.06 02:29
요번에 하는 프로젝트가 안도르이드에서 txt 파일을 가져와서 읽고, 수정한뒤에 저장하는 기능이 있었는데요,

처음엔 엑셀로 구현해놨다가 바껴서 txt 로 읽고 쓰기로 했습니다. 

처음 생각과는 달리 상당히 어려웠습니다. 문제점으로 제일 큰게 인코딩(encode)이었습니다.

안에 있는 데이터엔 한글이 포함되어 있었습니다. 아무런 인코딩 없이 아래와 같이 불러왔을때 한글이 이상한 문자로 깨지는 현상이 생겼습니다. 마름모에 물음표가 들어있는.ㅋㅋ(위키에서 살펴보니, UTF에서 글자를 못찾으면(?) 저 문자로 대체되거나 무시된다고 하는군요)

FileReader fr = new FileReader(src);
BufferedReader br = new BufferedReader(fr);
String line;
data = new ArrayList<String>();
while ((line = br.readLine()) != null) {
	Log.e("Flask_input", line);
	data.add(line);
}
br.close();
fr.close();
문제점을 찾기엔 너무 오래걸렸습니다...ㅠㅠ 먼저 인코딩관련 자료를 찾아보니 자바스크립트에서는 아주쉽게 http디코더였나? 에서 변환해주더군요.

일단 억지로 인코더/디코더 코드를 구해서 적용시켜봤지만, 인터넷 주소에서 쓰이는 %EF%AE%D6 뭐 이런 퍼센트가 들어가있는 문자가 나왔습니다...ㅠㅠ

다시 찾아보니, 이걸다시 변환해줘야;;;;;; 하지만 이게 원천적으로 문제를 해결할 수 없다는것을 깨닫고 다시 구글링을 했습니다.

그래서 구한게 파일을 읽어올때 바이트 코드로 읽는데, 여기에 인코딩해논것으로 읽어오기! 입니다.

File file = new File(src);
BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(file), "UTF-8"));
String line;
data = new ArrayList<String>();
while ((line = br.readLine()) != null) {
	Log.e("Flask_input", line);
	data.add(line);
}
br.close();
하지만,,,,,가끔 안되는게 있더군요.,.. 그래서 저기 UTF-8 로 되있는것을 EUC-KR로 바꿔보기도 하고 별의별 뻘짓을 해봤지만 아직 해결법은 못찾았습니다. (일단은 저 코드는 동작하는것 같습니다.)

뭐 여기까진 문제가 없었습니다. 그다음 txt에서 한줄을 읽고, 이걸 분해 하려고 substring() 를 사용했습니다.

그런데 이상한 현상이 생깁니다. 바로, subsitrng() 로 얻어온 문자열이 눈으로 볼땐 길이가 7인데, .length()찍어보면 8입니다....엉? 뭐야?

어....음.....머지.......................

하다가, 생각난 charAt()으로 해당 문자열 각각의 문자를 다 찍어보기로 합니다... 찍어보니, 맨 앞 자리가 아무것도 안나옵니다.... 아 뭐야;; 공백 문자인가...해서 int로 캐스팅하고 숫자를 찍어보니 65279 가 나왔습니다....ㅋㅋㅋㅋㅋㅋ아 뭐야.ㅋㅋㅋㅋ 이 숫자는 뭘 의미하는거야.ㅋㅋㅋㅋㅋㅋ

뭐 일단 char는 유니코드를 받으니, 16진수로 변환! 65279 -> 0xFEFF

저 16진수를 찾아보니 텍스트의 파일시작에서 '유니코드' 라고 말해주는 녀석이었습니다.

Big-endian : 0xFEFF
Little-endian : 0xFFFE

이라고 하는데, 자세한건 http://hyyoo.egloos.com/2273029 를 참고....

뭐 어쨋든, 파일의 첫 부분이 저 코드로 시작해서 첫줄의 인덱스가 하나씩 밀려서 글자 하나가 짤리게 되는 현상을 낳았네요....

드디어 문제를 해결하고... 이제 자러갑니다ㅠㅠ

+ 2012-2-7 관련 내용 추가

txt 파일을 출력하면 newLine()이 잘 안될때가 생기네요..

파일에서 맨 앞으로 가라는 CR(Carrge return) 과 다음 줄로 가라는 LF(Line Feed) 를 이용하여 엔터효과를 낼 수 있습니다.

 먼저 여기서 중요한 것이  LF 바로 개행 문자입니다.

아스키코드표에서 보면, 16진수 0x000A  가 개행문자입니다.

여기서 개행문자를 어떻게 주느냐?? 바로 케릭터 타입에담고, 줄 뒤에 붙여서 보내주면 됩니다! 참 쉽죠?

하지만 여기서 문제가 발생합니다. 바로 저 개행문의 유니코드값 '\u000a' 가 케릭터 타입에 안들어갑니다.
(\ 는 역 슬래시 입니다, 넣으려고 하면 오류를 보여줍니다.)

엥? 이게 무슨 소리야? 분명,  char a = '\u005a'  이런건 들어가는데?

찾아보니, 저것이 개행문자로 등록되어 있어서 넣을수(?) 없다느군요? 자세한건 나중에 추가하기로 하고...

그럼 이넘을 어떻게 넣어주느냐?  그냥 16진수 넣듯이 넣어주면 됩니다. 아래처럼 말이죠.
(자바에선  char 은 문자 지만, 숫자 값도 넣을 수 있습니다.)

 char a = 0x000A;

 그러면 정상적으로 들어가고

 String s = "hello world"+a;

 로 해주면 정상적으로 되는것을 확인하실수 있습니다.

자바에서 파일을 쓸때, 아니 윈도우에선 유닉스에서 만든  txt 파일들 가져오면  LF 가 짤려서 나온다고 합니다.
그래서 한줄한줄들이 장인의손길(?)에 의해 한땀한땀 이어진것을 보실수 있게 되는거죠.

의문이  생기는 것이  newLine() 를 해줬음에도 불구하고 개행이 안된다는 점입니다.

자바는 모든 플렛폼에서 구동되도록 설게되엇는뗴 말이죠, 그래서 각  OS 마다 다르게 내부적으로 적용(?)




저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Trackback 0 Comment 1
  1. Favicon of http://heather-hm.tistory.com BlogIcon HeatherHM 2015.02.11 22:59 신고 address edit & del reply

    댓굴 처음달아보네요 ㅋㅋ
    좋은글 감사합니다. 저도 똑같은 문제로 헤메고있었는데 마침 좋운글 잘 보고갑니다 ^^

2011.10.30 17:48
[자료구조]
큐 (Queue)


부대에서 자료구조에 관한 책을 잠깐 봤었는데, 몇몇 자료구조중 내가 써먹을 곳이 있어서 하나 구현해봤다.

아직 자료구조를 공부한게 아니고 추상적으로 '뭐 이런이런 개념..' 으로만 알고 있어서 실사용에는 뭔가 부족할것 같다.

일단, 구현한건 큐인데, 구현한 이유가, 자바에서 fps 표시를 할때 숫자의 변동이 심해서 몇인지 잘 보기 어렵다. 따라서 대략 60개 정도의 fps를 가져오고 이넘의 평균값을 표시하는것으로 했다.
(구현한 fps 측정이 허접하기 때문일 수 도 있지만;;; : 단순히 1프레임당 시스템 숫자 변동폭의 역수를 취해주는 방법으로 계산했음..;;) 


자주하는 게임인 카운터스트라이크 : 소스에 보면, fps를 표시하는 방법이 2개가 있다.  (net_ 제외하고.)

cl_showfps 1 과  
cl_showfps 2 인데, 이 둘의 차이점으론, 

1일땐 순간의 fps를 측정, 2일땐 평균값? 대충 0.5초간의 평균값을 말해주는것 같다. 자세히 보진 않았지만..ㅋ


따라서, 보기 편한것은 2일때가 되겠다. (위에서 적었듯이, 1은 변동이 심해서 무슨 숫자인지 보기 힘듬.) 

그래서 큐를 이용해서 구했다. (아, 내가 만든건 선형 큐)


큐의 특성? 은 FIFO(퍼스트 인 퍼스트 아웃) 라고들 하는데 그러니깐 먼저 들어간 사람이 먼저 나온다. 즉 줄 서서 기다릴때랑 똑같다.

그래서 fps를 계산할때도 먼저 들어간 값(오래된 값)먼저 지운다(dequeue). 가 되겠다.

그래서 실시간으로 갱신이 되지만, 쉽게 숫자를 인식 할 수 있는 법위인.. 뭐 그렇게 생각 할 수 있겠다.

나중에 스택을 구현해 보겠지만, 큐 구현이 맨땅에 헤딩하는식으로 만들어서 뭔가 좀 병맛이다...ㅠㅠ
(객체를 넣을때는 상관이 없는데, 객체를 불러와서 사용할땐, Object 타입이라서 다루기가 짜증난다. 예를들면, 숫자를 담아두었는데, 전체 데이터에 엑세스 할때 Object 라서 double 형 따위로 쉽게 변환이 안된다는것..

그래서 꼬꼼수로 toString 하고 Double 클래스의 valueOf로 다시 값을 읽어들이고...-_- 멍청한 짓하는건가.ㅋ 아님 자바로 이걸 만든다는게 좀 이상한건가;; C의 포인터같은게 없어서 뭔가 꼼수로 만든것 같다..ㅋ)


어쨋든 자바를 배우게 되면 다시한번 짜봐야 겠다.

일단, 코드..ㅋ

package utils;

import java.util.ArrayList;

public class Queue {
	
	protected int size;
	protected Object data[];
	protected int cur;
	
	
	public Queue(int $size){
		size = $size;
		data = new Object[$size];
		cur = $size-1;
		inits();
	}
	
	protected void inits(){
		int i=0;
		for(;i<size;i++){
			data[i] = null;
		}
	}
	
	public void initializeWith(Object init_value){
		for(int i=0;i<size;i++){
			data[i] = init_value;
		}
	}
	
	public Object enQueue(Object o){
		Object temp = data[cur];
		data[cur] = o;
		if(cur<=0) cur = size-1;
		else cur--;
		return temp;
	}
	
	public Object deQueue(){
		Object temp = data[cur];
		data[cur] = null;
		if(cur<=0) cur = size-1;
		else cur--;
		return temp;
	}
	
	public int getSize(){
		return size;
	}
	
	public Object[] getData(){
		return data.clone();
	}
	
	public void printData(){
		trace(data);
	}
	
	protected void set_cur(){
		cur--;
		if(cur<0) cur = size-1;
	}
	
	protected static void trace(Object ...args){
		int l = args.length-1, i=l;
		for(;i>0;i--){	System.out.print(args[i]+", ");	}
		System.out.println(args[0]);
	}
}

저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License

'[+++ JAVA +++] > - - Open Source' 카테고리의 다른 글

스택(Stack)  (0) 2012.11.14
(2012년 첫글은!?) [Blur] 블러 구현(java)2  (2) 2012.01.01
[Blur] 블러 구현(java)  (4) 2011.12.20
[자료구조] 자바로 만든 큐(Queue)  (1) 2011.10.30
Trackback 0 Comment 1
  1. Favicon of http://estellenotes.tistory.com BlogIcon 에스텔시아 2011.11.03 15:45 신고 address edit & del reply

    호오...자료구조 공부 열심히 해야겠네 ㅇㅅㅇ;;



티스토리 툴바